归并排序

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,INF=0x3f3f3f3f;
typedef long long LL;
LL n,a[N],b[N],ans;
void mergesort(int l,int r){
	if(l==r)return;
	int mid=l+r>>1;
	mergesort(l,mid);
	mergesort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j])b[k++] = a[i++];
		else b[k++] = a[j++],ans+=mid-i+1;
	}
	while(i<=mid)b[k++] = a[i++];
	while(j<=r)b[k++] = a[j++];
	for(int i=l;i<=r;i++)a[i] = b[i];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	mergesort(1,n);
	cout<<ans;
	return 0;
}