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

求逆序对一般使用归并排序的思想。

假设目前在递归过程中，左右两个子数组指针为l、r。由于归并排序是先排序左右子数组，所以此时左右子数组已经有序。当data[l] > data[r]时，根据左边子数组有序的性质，左子数组中下标在l之后的数也一定大于data[r]，从而l到左子数组末尾的数与data[r]都构成逆序对。

class Solution {
public:
    const int MOD = 1000000007;

    long long mergeSort(vector<int>& data, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        long long ln = mergeSort(data, l, mid), rn = mergeSort(data, mid + 1, r);
        long long res = (ln + rn) % MOD;
        vector<int> tmp;
        int il = l, ir = mid + 1;
        while (il <= mid && ir <= r) {
            if (data[il] < data[ir]) {
                tmp.push_back(data[il++]);
            }
            else {
                res = (res + mid - il + 1) % MOD;
                tmp.push_back(data[ir++]);
            }
        }
        while (il <= mid) {
            tmp.push_back(data[il++]);
        }
        while (ir <= r) {
            tmp.push_back(data[ir++]);
        }
        for (int i = 0; i < tmp.size(); i++) {
            data[l + i] = tmp[i];
        }
        return res;
    }

    int InversePairs(vector<int> data) {
        return (int)mergeSort(data, 0, data.size() - 1);
    }
};