题解

归并排序
答案=n*(n-1)/2-逆序对

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
long long n,a[maxn],b[maxn];
long long cnt;
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);
    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++];
            cnt+=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];
  	}
  	merge_sort(1,n);
  	cout<<(n*(n-1)/2)-cnt;
    return 0;
}