求解逆序对的个数(由归并排序衍生出的O(nlogn)时间复杂度的算法)

int count(int *a, int n) {
	int res = 0;
	for (int i=0; i<n-1; ++i) {
		for (int j=1; j<n; ++j) {
			if (a[i] > a[j]) res ++;
		}
	}
	return res;
}

#include <iostream>
using namespace std;

typedef long long ll;
const int N=1e5+10;
ll a[N], t[N];
ll res = 0;

void mergeSort(ll *a, int l, int r) {
	if (l>=r) return;
	int m = (r-l)/2 + l;
	mergeSort(a, l, m);
	mergeSort(a, m+1, r);
	//i为第一个区间的起始下标  第一个区间[l, m]
	//j为第二个区间的起始下标  第二个区间[m+1, r]
	//k为临时数组的起始下标
	int i = l, r = m+1, k = 0;
	while (i <= m && j <= r) {
		if (a[i] <= a[j]) t[k ++] = a[i ++];
		else {
			//a[i] > a[j] && i < j 构成了逆序对  而此时 a[i]到a[m]的所有元素均大于a[j]  
			//a[i,....,m]的长度为  m-i+1
			res += m-i+1;
			t[k ++] = a[j ++];
		}
	}	
	while (i <= m) t[k ++] = a[i ++];
	while (j <= r) t[k ++] = a[j ++];
	for (int i=l, k=0; i<=r; ++i, ++k) a[i] = t[k];
}


int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i=0; i<n; ++i) cin >> a[i];
	mergeSort(a, 0, n-1);
	cout << res << endl;
	return 0;
}