逆序对

关于归并排序求逆序对：

#include<iostream>
#include<cstdio>
using namespace std;
long long n,a[500005],ans=0;
long long f[500005];
void merge_sort(long long l,long long r)
{
    if(l==r)
     return;
     long long mid=(l+r)>>1;
     merge_sort(l,mid);
     merge_sort(mid+1,r);
     long long i=l,j=mid+1,p=l;
     while(i<=mid&&j<=r)
     {
        if(a[i]>a[j])
        {
            f[p++]=a[j++]; ans+=mid-i+1;
         }
         else f[p++]=a[i++];
     }
    while(i<=mid)
      f[p++]=a[i++];
    while(j<=r)
      f[p++]=a[j++];
    for(long long i=l;i<=r;i++)
     a[i]=f[i]; 
}
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
     scanf("%lld",&a[i]);
     merge_sort(1,n);
     printf("%lld\n",ans);
    return 0;
}

逆序对

原文：https://www.cnblogs.com/karryW/p/10914623.html