逆序对的数量

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 64MB，其他语言 128MB

描述

给定一个长度为 \(n\) 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 \(i\) 个和第 \(j\) 个元素，如果满足 \(i<j\) 且 \(a[i]>a[j]\)，则其为一个逆序对；否则不是。
数据范围 \(1≤n≤100000\)，数列中的元素的取值范围 \([0,10^9]\)。

输入描述

第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

输出描述

输出一个整数，表示逆序对的个数。

用例输入 1

6
2 3 4 5 6 1

用例输出 1

5

代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e5+5;
int n,a[N],c[N];
long long ans=0;

void _merge(int l1,int r1, int l2,int r2,int sc)
{
	int p1=l1,p2=l2,p3=sc-1;
	while(p1<=r1 && p2<=r2)
	{
		if(a[p1]<=a[p2])
		{
			c[++p3]=a[p1];
			p1++;
		}
		else
		{
			ans+=(r1-p1+1);
			c[++p3]=a[p2];
			p2++;
		}
	}
	while(p1<=r1) c[++p3]=a[p1], p1++;
	while(p2<=r2) c[++p3]=a[p2], p2++;
	return;
}

void merge_sort(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	_merge(l,mid, mid+1,r ,l);
	for(int i=l;i<=r;i++) a[i]=c[i];
	return;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	merge_sort(1,n);
	printf("%lld\n",ans);
	return 0;
}