题解 | 数组中的逆序对

#include <vector>
const int MOD = 1000000007;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    vector<int> w;

    int InversePairs(vector<int>& nums) {
        // write code here
        return merge_sort(nums, 0, nums.size() - 1);
    }

    long long merge_sort(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        long long ans = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
        w.clear();
        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) w.push_back(nums[i++]);
            else {
                w.push_back(nums[j++]);
                ans = (ans + (mid - i + 1)) % MOD;
            }
        }
        while (i <= mid) w.push_back(nums[i++]);
        while (j <= r) w.push_back(nums[j++]);
        for (i = l, j = 0; j < w.size(); i++, j++) nums[i] = w[j];
        return ans;
    }
};