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

借鉴了左程云大神算法课里面求小和的思路

public:
    long long  merge(vector<int>& nums,int L,int M,int R ){
        vector<int>help(R-L+1);
        int sum = 0;
        int i = 0;
        int p1 = L;
        int p2 = M+1;
        while(p1<=M&&p2<=R){
            sum += nums[p1]>nums[p2]?(M-p1+1):0;
            help[i++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];
        }
        while(p1<=M){
            help[i++] = nums[p1++];
        }
        while(p2<=R){
            help[i++] = nums[p2++];
        }
        for(int j=0;j<R-L+1;j++){
            nums[L+j] = help[j];
        }
        return sum;
    }
    long long  mergesort(vector<int>& nums,int L,int R){
        if(L == R) return 0;
        int M = L+((R-L)>>1);
        return mergesort(nums, L, M)+mergesort(nums, M+1, R)+merge(nums,L,M,R);
        
    }
    int InversePairs(vector<int> data) {
        int L = 0;
        int R = data.size()-1;
        return mergesort(data, L, R)%1000000007;
    }
};