归并算法实现求解逆序对【模板】

#include<stdio.h>
#define LL long long //以后可以考虑这样写 简洁

int n,i,a[500010], b[500010];
//需要开辟两个数组

LL count(int l,int r)//统计[l ,r]的逆序对数
{
    LL s=0;//初始化
    int mid=(l+r)/2, i=l, j=mid+1, k=l;
    //printf("%d \n", mid );

    if (l<mid) s+=count(l,mid);//计算累加左区间的逆序对
    if (mid+1<r) s+=count(mid+1,r);//计算累加右区间的逆序对

    while( i<=mid || j<=r )
    {
        while ( i<=mid && (j>r || a[i]<=a[j]) ){
            //printf("%d < %d", a[i], a[j] ); //左边理应小于右边（左边等级低 右边等级高）
            b[k++]=a[i++];
        }
        while ( j<=r && (i>mid || a[j]<a[i]) )
        {                        //右边的大于左边的进行计数
           // printf(" %d-<-%d ", a[j], a[i] );
            b[k++]=a[j++];
            s+=mid-i+1;
        }
    }
    for(i=l;i<=r;i++)
        a[i]=b[i];
    return s;
}

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