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

class Solution {
  public:
    long res = 0;
    long kmod = 1000000007;
    void merge(int lo, int mi, int hi, vector<int>& arr) {
        vector<int> b;
        b.assign(arr.begin() + lo, arr.begin() + mi);
        int lb = mi - lo;
        int lc = hi - mi;
        for (int i = 0, j = 0, k = 0; (j < lb) or (k < lc); ) {
            if (j < lb and (lc <= k or b[j] <= arr[mi + k]))
                arr[lo + i++] = b[j++];
            if (k < lc and (lb <= j or arr[mi + k] < b[j])) {   // 右边比左边大
                if (j < lb) {
                    res += (lb - j);    // 加的是左边区间的剩余元素个数
                    res %= kmod;
                }
                arr[lo + i++] = arr[mi + k++];
            }
                
        }
    }

    void mergeSort(int lo, int hi, vector<int>& arr) {
        if (hi - lo < 2) return;
        int mi = (lo + hi) >> 1;
        mergeSort(lo, mi, arr);
        mergeSort(mi, hi, arr);
        merge(lo, mi, hi, arr);
    }
    int InversePairs(vector<int> data) {
        mergeSort(0, data.size(), data);
        return res;
    }
};

归并排序，只要右区间有元素被调整到了前面，且左区间还有元素的情况下，就证明有逆序对存在，res加的值就是左区间剩余元素的个数。