逆序数 （C++代码）（树状数组 O(nlogn) ）

解题思路:

        离散化 + 树状数组

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 1024;
struct datas {
	int num, dis;
} Num[SIZE];
int BIT[SIZE], total;

bool cmp(datas A, datas B) {
	return A.num < B.num;
}

int query(int L) {
	int res = 0;
	while (L) {
		res += BIT[L];
		L -= L & (-L);
	}
	return res;
}

void updata(int pos, int V) {
	while (pos <= total) {
		BIT[pos] += V;
		pos += pos & (-pos);
	}
}

int main() {
	scanf("%d", &total);
	for (int i = 1; i <= total; i++) {
		scanf("%d", &Num[i].num); Num[i].dis = i;
	}
	sort(Num + 1, Num + total + 1, cmp);
	
	for (int pos = 1; pos <= total; pos++)
		updata(pos, 1);
		
	int ans = 0;
	for (int i = 1; i <= total; i++) {
		ans += query(Num[i].dis - 1);
		updata(Num[i].dis, -1);
	}
	printf("%d", ans);
}