逆序对

在归并排序的基础
左边的逆序对
有变的逆序对
右区间小于左区间的
排完顺序之后每次合并取右边的就加上左边区间的长度就行了。

//求逆序对
#include<bits/stdc++.h>
using namespace std;
int merge_sort(int *A,int x,int y,int *T){
    int cnt = 0;
    if(x < y){//保证最少要有两个元素否则死循环
        int m = (x + y) / 2;//划分
        cnt += merge_sort(A,x,m,T);//递归求解
        cnt += merge_sort(A,m + 1,y,T);

        int p = x,q = m + 1,i = x;
        while(p <= m && q <= y){
            if(A[p] <= A[q])T[i++] = A[p++];
            else {
                T[i++] = A[q++];
                cnt += (m - p + 1);
            }
        }
        while(p <= m)T[i++] = A[p++];
        while(q <= y)T[i++] = A[q++];
        //上面的三句话合成一句话
        /*while(p <= m || q <= y){
            if(q > y || (p <= m && A[p] <= A[q]))T[i++] = A[p++];
            else T[i++] = A[q++];
        }*/
        for(i = x;i <= y;i++)A[i] = T[i];
        return cnt;
    }
    return cnt;
}
int main()
{
    int *tmp = new int[9];
    int a[] = {2,4,-7,5,2,-1,2,-4,3,1};
    printf("%d\n",merge_sort(a,0,9,tmp));
    for(int i = 0;i < 9;i++){
        printf("%d ",a[i]);
    }
    printf("%d\n",a[9]);
    delete tmp;
}