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

class Solution {
private:
int kmod = 1000000007;

public:
    int InversePairs(vector<int> data) {
        if(data.size() == 0 || data.size() == 1) return 0;
        int l = 0,r = data.size() - 1,mid = (r - l) >> 1; 
        vector<int> kmp(data.size(),0);
        int res = 0;
        Sort(data,kmp,l,r,res);
        return res;
    }

    void Sort(vector<int>& arr,vector<int>& kmp,int l,int r,int &res){
        if(l >= r) return;
        int mid = l + ((r - l) >> 1);
        Sort(arr,kmp,l,mid,res);
        Sort(arr,kmp,mid + 1,r,res);
        Merge(arr,kmp,l,mid,r,res);
    }

    void Merge(vector<int>& arr,vector<int>& kmp,int l,int mid, int r,int &res){
        int i = l,j = mid + 1,k = l;
        while(i <= mid && j <= r){
            if(arr[i] > arr[j]){
                kmp[k ++] = arr[j ++];
                res += (mid - i + 1);
                res %= kmod;
            }
            else {
                kmp[k ++] = arr[i ++];
            }
        }

        while(i <= mid){
            kmp[k ++] = arr[i ++];
        }
        while(j <= r){
            kmp[k ++] = arr[j ++];
        }
        for(int m = l;m <= r;m ++){
            arr[m] = kmp[m];
        }
    }

};

跟着题解手打一遍归并排序，自己再打一遍。