题解 | #求逆序数#

归并排序，遇到逆序就记录

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+3;
typedef pair<int,int> pii;
typedef long long ll;
int a[N],b[N];
int res;

void mesort(int a[],int l,int r)
{
	if(l==r)return ;
	int mid=l+r>>1;
	mesort(a,l,mid),mesort(a,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])b[k++]=a[i++];
		else
		{
			b[k++]=a[j++];
			res+=mid-i+1;//记录逆序数量
		}
	}
	while(i<=mid)b[k++]=a[i++];
	while(j<=r)b[k++]=a[j++];
	for(int i=l,j=0;i<=r;i++)
	a[i]=b[j++];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);

	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	mesort(a,1,n);
	cout<<res;
		
	return 0;
}