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

class Solution {
public:
    const int M = 1000000007;
    using LL =  long long;
    LL merge(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) return 0;

        int m = (l + r) >> 1;
        LL res = merge(nums, tmp, l, m) + merge(nums, tmp, m + 1, r);
        // 归并
        int k = 0, i = l, j = m + 1;
        while (i <= m && j <= r) {
            if (nums[i] > nums[j]) {
                tmp[k++] = nums[j++];
                res += (m - i + 1);
                res %= M;
            } else {
                tmp[k++] = nums[i++];
            }
        }
        while (i <= m) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (int i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];

        return res;
    }

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