归并排序

在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。
可以参考acwing的题解：AcWing 788. 【算法基础课】逆序对的数量（归并排序） – AcWing

#include <vector>
class Solution {
public:
    long long merge(vector<int>& a, int l, int r, vector<int>& tmp){
        if( l == r) return 0;
        int mid = l + r >> 1;
        long long res = (merge(a, l, mid, tmp) + merge(a, mid+1, r,tmp)) % 1000000007;
        
        int i = l;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= r){
            if(a[i] <= a[j]) tmp[k++] = a[i++];
            else{
                tmp[k++] = a[j++];
                //是逆序对 结果累加
                res += mid - i + 1;
            }
        }
        // 处理剩余的
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        for(int i = 0, j = l; j<=r; i++, j++){
            a[j] = tmp[i];
        }
        return res % 1000000007;
    }

    int InversePairs(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        // tmp用以暂存合并后的结果
        vector<int> tmp(nums.size());
        return merge(nums, 0, nums.size() - 1, tmp);
    }
};