题解 | 数组中的逆序对

class Solution {
public:
    int InversePairs(vector<int>& nums) {
       int size = nums.size();
       if (size<=1) return 0;
       vector<int> temp(size);
       return meregSort(nums,temp,0,size-1)%1000000007;
    }
private:
    long long meregSort(vector<int>& nums, vector<int>& temp, int l, int r) {
        if (l>=r) return 0;
        int mid = l+(r-l)/2;
        long long count = (meregSort(nums, temp, l, mid)+meregSort(nums, temp, mid+1, r))%1000000007;
        int i = l, j = mid+1, k = l;
        while (i<=mid&&j<=r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                count += (mid-i+1)%1000000007;
            }
        }
        while (i<=mid) {
            temp[k++] = nums[i++];
        } 
        while (j<=r) {
            temp[k++] = nums[j++];
        }
        for (int a = l; a<=r; ++a) {
            nums[a] = temp[a];
        }
        return count;
    }
};