题解 | 数组中的逆序对

通过归并排序统计逆序对的方法

左半部分 [l, mid] 已经是递增序列

右半部分 [mid+1, r]也是递增序列

但是当它们合并在一起时可能会形成逆序对，i在左半部分，j在右半部分。

nums[j] < nums[i]时，nums[j]肯定大于nums[i]之前的所有数（否则早就加到tmp里了，也不会等到现在）。这个时候意味着，nums[i + 1], nums[i + 2], nums[i + 3]......都大于nums[j](因为左半部分递增，nums[i]你都不大于，剩下的咋可能大于)，但是同时nums[j]是比右半部分的nums[j - 1], nums[j - 2]...那些大（也因为右半部分递增）。所以逆序对的数量就是 i 到 mid 中间那些大于j的数，包括i和mid，所以是i - mid + 1。

动笔画一下就明白了。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    const int MOD = 1e9 + 7;
    vector<int> tmp;
    long long mergesort(vector<int>& nums, int l, int r) {
        if(l >= r) return 0;
        int mid = l + r >> 1;
        long long res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) tmp[k ++] = nums[i ++];
            else {
                tmp[k ++] = nums[j ++]; 
                res = (res + mid - i + 1) % MOD;
            }
        }
        while(i <= mid) tmp[k ++] = nums[i ++];
        while(j <= r) tmp[k ++] = nums[j ++];
        for(int i = l, j = 0; i <= r; i ++, j ++) nums[i] = tmp[j];
        return res;
    }

    int InversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergesort(nums, 0, nums.size() - 1);
    }
};