题解 | 数组中的逆序对

class Solution {
  public:
  //利用归并排序进行逆序对的计数
  //容易错误之处：用于比较的临时数组temp应当在递归函数内建立，而不是传一个临时数组的引用到函数内。这样能每次递归都使子函数有序，用排列好的子数组计算逆序对才有意义，否则res+=mid-i+1计算逆序对的方法就是错误的（因为这种计算方法是基于有序子数组）
    int mod=int(1e9+7);
    int InversePairs(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        vector <int> temp(nums.size());
        return MergeSort(left, right, nums, temp);
    }
    int MergeSort(int left, int right, vector <int>& data, vector <int>& temp) {
        if (left >= right)return 0;
        int mid = left + ((right - left) >> 1);
        int res = MergeSort(left, mid, data, temp) + MergeSort(mid + 1, right, data,temp);
        res%=mod;
        for (int k = left; k <= right; k++) temp[k] = data[k];
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1)data[k] = temp[j++];
            else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++];
            else {
                res += mid - i + 1, data[k] = temp[j++];
            }
        }
        return res%mod;

    }
};