求逆序对（归并）

求逆序数对（归并解法）

简述

题目链接：https://www.luogu.com.cn/problem/P1908
这题主要是运用到逆序数排序是的数组有序性，那么逆序数对就是满足逆序数条件的那个数前面有多少个，然后全部加起来就可以了。

代码

#include <stdio.h>
#define ll long long int
#define maxn 500010
ll ans = 0;
ll temp[maxn] = { 0 }; //该数组用于Msort函数，保存临时结果
void Msort(ll *s, ll left, ll mid, ll right) { //该函数用于排序，主要是将一个数组看成两部分进行比较
	ll i = left, j = mid + 1, k = left;
	while (i <= mid && j <= right) { //该循环是归并排序关键部分，主要是两部分进行比较，小的放前面
		if (s[i] <= s[j]) {
			temp[k++] = s[i++];
		}
		else {
			ans += mid - i + 1; //这是用归并求逆序数最关键的一步，也就这一步
			temp[k++] = s[j++];
		}
	}
	while (i <= mid) { temp[k++] = s[i++]; } //两部分中有一部分没历遍完，就要用到这两个循环
	while (j <= right) { temp[k++] = s[j++]; }
	for (i = left; i <= right; i++) { //将最后结果放入原数组
		s[i] = temp[i];
	}
}
void Merge(ll *s, ll left, ll right) { //该函数用于数组拆分
	if (left >= right) { //结束条件
		return;
	}
	ll mid = (left + right) >> 1; //取中间值
	Merge(s, left, mid); //左半部
	Merge(s, mid + 1, right); //右半部
	Msort(s, left, mid, right); //调用Msort函数，进行排序
}
ll s[maxn] = { 0 };
int main() {
	ll t;
	while (~scanf("%lld", &t)) {
		while (t-- > 0) {
			ll n;
			scanf("%lld", &n);
			for (ll i = 1; i <= n; i++) {
				scanf("%lld", s + i);
			}
			ans = 0; //ans为全局变量，每次调用需要给它重新赋值
			Merge(s, 1, n);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

解释

ans += mid - i + 1; //这是用归并求逆序数最关键的一步，也就这一步
比如 1 3 2
就会被拆成 1 3 为一对；2 为一对；然后再拆成1，3，2各为一队，之后在和；
先1和3比较，结果没变，所以ans没有变，然后就是1 3和2进行比较，其中 3 和 2满足逆序数条件，
就计算3那个位置前面有多少个数，所以答案为1；
可能不是清楚，有问题可以私聊我！