正经题解｜逆序对

【算法分析】

举个例子：将下面两个区间排序
ai：3 4 7 9
R1 = 4
aj: 1 5 8 10
首先将右区间的1取出，放在 tmp 中，此时 1 比每个ai中的元素都小，得到的逆序对的数量是4。tmp：1

然后再将ai和aj比较（直到ai<aj)，ai<aj时将ai的元素发在tmp中。tmp：1 3 4

现在aj>ai,i指向a3的位置，将5放在tmp中，得到的逆序对的数量为2。tmp: 1 3 4 5

以此类推，直到进行完归并排序，每次合并都会求出逆序对的数目为：R1-i+1，最后让 ans 加上R1-i+1得到答案。

【参考代码】

#include <iostream>
using namespace std;

const int N = 5e5 + 10;
int a[N], tmp[N];
long long n, ans;

//a的[L1,R1] 和 [L2,R2] 做归并 
void Merge(int a[], int L1, int R1, int L2, int R2) {
	int i = L1, j = L2;
	int cnt = 0;
	while (i <= R1 && j <= R2) {
		if (a[i] <= a[j]) tmp[cnt++] = a[i++];
		else tmp[cnt++] = a[j++], ans += R1 - i + 1; 
	}
	//左半段剩余的元素
	while (i <= R1) tmp[cnt++] = a[i++];
	//右半段剩余的元素 
	while (j <= R2) tmp[cnt++] = a[j++];
	//0~cnt-1，tmp复制到a 
	for (int i = 0; i < cnt; i++) {
		a[L1 + i] = tmp[i];
	}
}

void MergeSort(int a[], int l, int r) {
	if (l >= r) return; //只有一个元素，划分结束，返回
	int mid = (l + r) / 2;
	MergeSort(a, l, mid); //递归处理左半边[l,mid]
	MergeSort(a, mid + 1, r);//递归处理右半边[mid+1,r]
	Merge(a, l, mid, mid + 1, r);//两个半边做归并 
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	MergeSort(a, 1, n);
	cout << ans;
	return 0;
}

【时间复杂度】

$O(nlog_2n)$

【预计得分】

$100pts$