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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        int right = nums.size() - 1;
        int left = 0;
        return merge(nums, left, right);
    }

    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;
        int mid = (l + r) >> 1;
        int ls = merge(nums, l, mid);
        int rs = merge(nums, mid + 1, r);
        int cs = merge_sort(nums, l, mid, r);
        return (ls + rs + cs) % 1000000007; // 防止溢出
    }

    int merge_sort(vector<int>& nums, int l, int mid, int r) {
        int i = l, j = mid + 1, sum = 0, k = 0;
        vector<int> help(r - l + 1);

        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                sum += mid - i + 1;
                sum %= 1000000007; // 防止溢出
                help[k++] = nums[j++];
            } else {
                help[k++] = nums[i++];
            }
        }

        while (i <= mid) {
            help[k++] = nums[i++];
        }
        while (j <= r) {
            help[k++] = nums[j++];
        }

        for (int i = 0; i < help.size(); i++) {
            nums[l + i] = help[i];
        }
        return sum;
    }
};