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

class Solution {
public:
    const int P = 1000000007;

    int merge(vector<int> &data, int l, int r){   //y总的归并排序
        if(l >= r) return 0;   //一个数  直接返回
        int mid = (l + r) >> 1;
        int res = merge(data, l, mid) + merge(data, mid + 1, r);  //两个子区间内部先找
        int i = l , j = mid + 1;
        vector<int> temp;   //记录当前大区间内部的归并结果
        while(i <= mid && j <= r){
            if(data[i] <= data[j]) temp.push_back(data[i ++]);
            else {
                temp.push_back(data[j ++]);
                res += mid - i + 1;     //两个字区间之间找，这两个子区间已经各自有序
                if(res >= P) res %= P;
            }
        }
        while(i <= mid) temp.push_back(data[i ++]);  //对于另一个没遍历完的子区间，直接排到后面
        while(j <= r) temp.push_back(data[j ++]);
        i = l;
        for(auto x : temp) data[i ++] = x;   //temp放回原来的归并序列，本次归并完成
        return res;
    }

    int InversePairs(vector<int> data) {
        return merge(data, 0, data.size()-1);
    }
};