归并排序求逆序对

鸣谢：感谢zyf神犇告诉了我怎么用归并排序求逆序对！
另：这是我的第一份归并排序的代码，也是第一份求逆序对的代码

1. 什么是逆序对

对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称 (A[ i] ,A[ j] ) 为数组 A 中的一个逆序对。
例如，数组（3，1，4，5，2）的逆序对有 (3,1),(3,2),(4,2),(5,2)，共 4 个。
摘自度娘百科

2. 怎么用归并排序求逆序对

我们其实只要在归并排序的代码上加一句话就可以实现求逆序对了。

归并排序中，在合并左右两个区间时，对于右区间的每一个数字 a[i]，在左区间中有 n[i] 个比 a[i] 小的数字，那么 n[1]+n[2]+n[3]+… 就是跨越左右区间的逆序对数。而我们除了要求出跨越左右区间的逆序对数，还要求出左区间有多少对、右区间有多少对，这个我们就用递归实现。具体看代码吧，很难口头讲清楚。

3. 例题&代码

1. 求逆序对 codvs – 1688
   传送门=￣ω￣=
   思路：模板题。
   代码：

#include <cstdio>
int n,arr[100005],c[100005],d[100005];
long long ans;
void mersort(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1,a=l,b=m+1,cnt=l;
    mersort(l,m),mersort(m+1,r);
    c[m+1]=d[r+1]=1000000000;
    for(int i=l;i<=m;i++)c[i]=arr[i];
    for(int i=m+1;i<=r;i++)d[i]=arr[i];
    while(a<=m||b<=r)
        if(c[a]<=d[b])arr[cnt++]=c[a++];
        else arr[cnt++]=d[b++],ans+=(long long)(m-a+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    mersort(1,n);
    printf("%lld",ans);
    return 0;
}

1. hzwer 与逆序对 codevs – 4163
   传送门=￣ω￣=
   思路：同样模板题，数据大小大了 10 倍而已。
   代码：

#include <cstdio>
int n,arr[1000005],c[1000005],d[1000005];
long long ans;
void mersort(int l,int r)
{
    if(l==r)return;
    int m=(l+r)>>1,a=l,b=m+1,cnt=l;
    mersort(l,m),mersort(m+1,r);
    c[m+1]=d[r+1]=1000000000;
    for(int i=l;i<=m;i++)c[i]=arr[i];
    for(int i=m+1;i<=r;i++)d[i]=arr[i];
    while(a<=m||b<=r)
        if(c[a]<=d[b])arr[cnt++]=c[a++];
        else arr[cnt++]=d[b++],ans+=(long long)(m-a+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    mersort(1,n);
    printf("%lld",ans);
    return 0;
}