题解 | #数组中的逆序对#

public:
    int temp[100005];
    int InversePairs(vector<int> data) {
        vector<int>copy;
        for(int i=0;i<data.size();i++){//先保存下来
            copy.push_back(data[i]);
        }
        return InversePairs1(data,0,data.size()-1);
    }
    int InversePairs1(vector<int> &data,int left,int right){
        if(left==right)return 0;//递归到只有一个数
        int mid=(left+right)/2;//先进行分治递归
        //遍历左右子树，直至只有一个数
        int leftInversePairs1=InversePairs1(data,left,mid);
        int rightInversePairs1=InversePairs1(data,mid+1,right);
        //左右子树都是有序的，逆序对在合并的过程中计算
        int  merge=merge_sort(data,left,mid,right);
        return (leftInversePairs1+rightInversePairs1+merge)%1000000007;
    }
    int merge_sort(vector<int> &data,int left,int mid,int right){
        for(int i=left;i<=right;i++){
            temp[i] = data[i];//把所有值赋给临时数组，等下归并时要用
        }
        int i=left;
        int j=mid+1;
        int count=0;
        //通过双指针比较 对两段数进行排序，并计算逆序对
        for(int k=left;k<=right;k++){
            if(mid+1==i){//左端先完
                data[k]=temp[j];
                j++;
            }else if(j==right+1){
                data[k]=temp[i];//右端先完
                i++;
            }else if(temp[i]<=temp[j]){
                data[k]=temp[i];
                i++;
            }
            else if(temp[i]>temp[j]){
                data[k]=temp[j];
                count+=(mid+1-i);
                j++;
            }
        
        }
        return count%1000000007;//不模不行
    }
};