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

class Solution {
private:
    int res = 0;
    int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> temp(n);
        sort_(data, temp, 0, n-1);
        return res;
    }
    
    void sort_(vector<int>& data, vector<int>& temp, int l, int r){
        if(l >= r){
            return;
        }
        int mid = l + (r - l)/2;
        sort_(data, temp, l, mid);
        sort_(data, temp, mid+1, r);
        merge(data, temp, l, mid, r);
    }
    
    void merge(vector<int>& data, vector<int>& temp, int l, int mid, int r){
        int t = l;
        int i = l, j = mid+1;
        while(i <= mid && j <= r){
            if(data[i] > data[j]){
                temp[t] = data[j];
                t++; j++;
                res += (mid - i + 1);
                res = res % kmod;
            }
            else{
                temp[t] = data[i];
                t++; i++;
            }
        }
        while(i <= mid){
            temp[t] = data[i];
            t++; i++;
        }
        while(j <= r){
            temp[t] = data[j];
            t++; j++;
        }
        
        for(int i=l; i<=r; i++){
            data[i] = temp[i];
        }
        
    }
    
};