【算法笔记：归并排序+逆序对】求逆序对

题目来源：

洛谷P1908 逆序对
WUSTOJ 1850 求逆序对
题目描述：

1003: 求逆序对
给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
Input
第一行为n,表示序列长度，接下来的一行包含n个整数（A1，A2，…，An），表示序列中的n个数。
N<=105，Ai<=1055，Ai<=105
Output
输出所有逆序对总数。
Sample Input
4
3 2 3 2
Sample Output
3

思路：归并排序
其排序原理我也就不多说了，网上也是烂大街的代码和讲解，不清楚的可以去网上找找看。而逆序对求解过程可以在归并排序中进行。即：对于左：l —— m和右：m+1 —— r两个子区间，每次肯定都是各自已经排好序了的，剩余任务就是将两个区间整合。而在整合时，若右区间某元素y与左区间某元素x成逆序对，则y与x左侧所有元素都成逆序对，加上x及x左侧所有元素即可。

由于洛谷数据要求比wustoj大，故此处直接上洛谷代码吧（总之两个都能AC就是了）。

    #include<cstdio>
    #include<cstring>
    int n,a[500010],t[500010];
    long long tot=0;
    void msort(int l,int r)//对a[]在x，y 下标范围的元素进行归并排序求解逆序对
    {
        if(l==r)return;//不可再分时返回
        int m=(l+r)/2;
        int i=l,j=m+1,p=l;
        msort(l,m);msort(m+1,r);
        while(i<=m||j<=r)
        {
            if(j>r||(i<=m&&a[i]<=a[j]) ) t[p++]=a[i++];//说明i还没有到端点，加上左区间的值；又或者满足条件，不是逆序对，加入左区间值
            else { t[p++]=a[j++]; tot+=m-i+1; }//如果是的话，则该数即该数左侧的所有元素都与这个数成逆序对
        }
        for(i=l;i<=r;i++) a[i]=t[i];
     }
    
    int main()
    {
        while(~scanf("%d",&n))
        {
            tot=0;
            memset(a,0,sizeof a);
            memset(t,0,sizeof t);
            for(int i=1;i<=n;i++) 
            scanf("%d",&a[i]);
            msort(1,n);
            printf("%lld\n",tot);
         }
         return 0;
    }