归并排序求逆序对

题目大意

t组数据

昨天比赛的时候居然忘记了逆序对怎么求...罪过罪过...

当归并过程中，如果右集合的元素进入到新集合中，说明左集合中剩下的元素都比该元素大，那么ans+=左边集合剩下的元素

Code

#include<string>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define MOD 100000007
#define PI 3.1415926535898
#define INF 0x3f3f3f3f
#define MAXN 1000050
const double EPS = 1e-8;
LL read()
{
	LL x = 0, w = 1;
	char ch = 0;
	while (ch < ‘0‘ || ch>‘9‘)
	{
		if (ch == ‘-‘)
		{
			w = -1;
		}
		ch = getchar();
	}
	while (ch >= ‘0‘ && ch <= ‘9‘)
	{
		x = x * 10 + ch - ‘0‘;
		ch = getchar();
	}
	return w * x;
}
LL n, a[1000050],ans[1000050],sum;
void msort(int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	msort(l, mid - 1);
	msort(mid, r);
	int nl = l;
	int nr = mid;
	int now = l;
	while (nl < mid && nr <= r)
	{
		if (a[nl] > a[nr])
		{
			sum += mid - nl;
			sum %= MOD;
			ans[now++] = a[nr];
			nr++;
		}
		else
		{
			ans[now++] = a[nl];
			nl++;
		}
	}
	while (nl < mid)
	{
		ans[now++] = a[nl];
		nl++;
	}
	while (nr <= r)
	{
		ans[now++] = a[nr];
		nr++;
	}
	for (register int i = l; i <now; i++)
	{
		a[i] = ans[i];
	}
}
int main()
{
	n = read();
	for (register int i = 1; i <= n; i++)
	{
		a[i] = read();
	}
	msort(1, n);
	cout << sum << endl;
	return 0;
}

归并排序求逆序对

原文：https://www.cnblogs.com/lumingran/p/14063448.html