逆序对的求法

使用归并排序求逆序对的时候总是犯错。

假如对于数据a[l~r] 中，a[l,mid],a[mid+1,r]已经分别有序，i,j指针分别是前后两个区间的指针

当a[i]>a[j]时，a[l~Mid]中的元素，从i开始（包括i），到mid，均能够和a[j]形成逆序对,个数为mid-i+1

而不是a[i]均可和a[mid+1~j]形成逆序对（这样会造成重复计算）

例如前半部分为3，后半部分为1，2； 前一种计算方法是1+1，后一种计算方法会得到1+2，多算了

一个示例代码；

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+5;
int n;
int a[N],t[N];
typedef long long LL;

LL ms(int l,int r)
{
    if(l>=r)return 0;

    LL res=0;
    int mid=l+r>>1;
    res =ms(l,mid)+ms(mid+1,r);

    int i=l,j=mid+1;
    int k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j]) 
        {
            res+=mid-i+1;
            t[k++]= a[j++];
        }
        else 
        {
            t[k++]=a[i++];
        }
    }
    while(i<=mid) t[k++] = a[i++];
    while(j<=r) t[k++] = a[j++];

    for(int i=l,h=0;i<=r;i++)a[i] = t[h++];

    return res;

}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )scanf("%d ",&a[i]);
    cout<<ms(0,n-1);
    return 0;
}