牛客网：数组中的逆序对

这里和之前的leetcode上面的逆序对不一样的点在于，这里要取膜。

具体思路可以看

剑指offer51:数组中的逆序对_lsgoose的博客-CSDN博客

不过这里有一个很奇怪的点在于取模：

代码如下：

class Solution {
    private:
    const int kmod=1000000007;
public:
    int InversePairs(vector data) {
        vector tmp(data.size());
        return mergeSort(data, tmp, 0, data.size()-1);
    }
    int mergeSort(vector&nums,vector&tmp,int l,int r){
        if(l>=r) return 0;
        int mid=l+((r-l)>>1);
        int num=mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid+1, r);
        int left=l, right=mid+1, pos=l;
        while(left<=mid && right<=r){
            if(nums[left]<=nums[right]){
                tmp[pos]=nums[left++];
            }else{
                num+=mid-left+1;
                num%=kmod;
                tmp[pos]=nums[right++];
            }
            ++pos;
        }
        while(left<=mid){
            tmp[pos++]=nums[left++];
        }
        while(right<=r){
            tmp[pos++]=nums[right++];
        }
        copy(tmp.begin()+l, tmp.begin()+r+1, nums.begin()+l);
        return num;
    }
};

这里的num先相加再取模和先去摸再相加结果不一样。

为什么呢，因为先取模再相加会溢出哒