並べ替えを行い、逆順対数を求める(他の2つの姿勢BIT線分樹を添付)

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
const int maxn = 2e5 + 7;
int a[maxn], b[maxn];
long long cnt;
//         cnt      ， 1   。 ary[l：r]  ，     ，ary = des
void merge_sort(int ary[], int l, int r, int des[]) { // ary[l..r]       
	if (l >= r) return;
	int mid = (l + r) >> 1;
	merge_sort(ary, l, mid, des);
	merge_sort(ary, mid + 1, r, des);
	int i = l, j = mid + 1, cur = l; //     
	while (i <= mid && j <= r) {
		if (ary[i] <= ary[j]) {
			des[cur++] = ary[i++];
		}			
		else { //   ，ary[i] > ary[j], ary[j]    （ ） 
			des[cur++] = ary[j++];
			cnt += mid - i + 1; //     
			// ary[i] > ary[j] ，       ary[i]     ary[j] ， ary[j]  ary[i]    ，      mid + 1 - i
		}
	}
	while (i <= mid) {
		des[cur++] = ary[i++];
	}
	while (j <= r) {
		des[cur++] = ary[j++];
	}
	memcpy(ary + l, des + l, sizeof(int) * (r - l + 1));
} 

int main()
{
	int T;
	scanf("%d", &T);
	for (int k = 1; k <= T; ++k) {
		int n;
		scanf("%d", &n);
		cnt = 0;
		for (int i = 0; i < n; ++i)
			scanf("%d", a + i);
		merge_sort(a, 0, n - 1, b);
		//printf("%d", b[0]);
		//for (int i = 1; i < n; ++i)
		//	printf(" %d", b[i]);
		//puts(""); //          
		//printf("Scenario #%d:
%d

", k, cnt); //poj1804    ,poj      ，int    
		printf("%lld
", cnt); //http://www.spoj.com/problems/INVCNT/en/
	}


	return 0;
}

#include 
#include 
#define ADD 1000001
#define M 2000001
#define N 1007 
using namespace std;
int ary[N], bit[M + 1], n;
int lowbit(int x) {
	return x & (-x);
}
void add(int pos, int val) {
	while(pos <= M) { //pos <= ?
		bit[pos] += val;
		pos += lowbit(pos);
	}
}

int sum(int pos) { //  1:pos   
	int res = 0;
	while(pos > 0) {
		res += bit[pos];
		pos -= lowbit(pos);
	}
	return res;
}

int main() {
	int T, kase = 0;
	scanf("%d", &T);
	while (T-- > 0) {
		memset(bit, 0, sizeof bit);
		scanf("%d", &n);
		long long ans = 0; 
		for (int i = 0; i < n; ++i) {
			scanf("%d", ary + i);
			ary[i] += ADD;
			ans += (i - sum(ary[i])); //       
			add(ary[i], 1);
		}
		printf("Scenario #%d:
%lld

", ++kase, ans);
		
	} 
	
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
using namespace std;
const int N = 5007;
int segTree[N << 1], ary[N];
void build(int rt, int l, int r) {
	segTree[rt] = 0;
	if (l == r) return;
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
}
void update(int rt, int l, int r, int pos) {
	if (l == r) {
		segTree[rt]++; //       ，   1
		return;
	}
	int mid = l + r >> 1;
	if (pos <= mid)
		update(rt << 1, l, mid, pos);
	else update(rt << 1 | 1, mid + 1, r, pos);
	segTree[rt] = segTree[rt << 1] + segTree[rt << 1 | 1]; //        
}
int query(int rt, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		return segTree[rt];
	}
	int mid = l + r >> 1, res = 0;
	if (L <= mid)
		res += query(rt << 1, l, mid, L, R);
	if (R > mid)
		res += query(rt << 1 | 1, mid + 1, r, L, R);
	return res;
}
int main()
{
	int n;
	while (~scanf("%d", &n)) {
		memset(segTree, 0, sizeof segTree);
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%d", ary + i);
			cnt += query(1, 0, n - 1, ary[i], n - 1);
			update(1, 0, n - 1, ary[i]); //    
		}
		int minCnt = cnt;
		for (int i = 0; i < n; ++i) {
			cnt += n - ary[i] - ary[i] - 1; //                     ，     ary[i] 0:n-1     
			minCnt = min(minCnt, cnt);
		}
		printf("%d
", minCnt);
	}

	return 0;
}