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

class Solution {
public:
    int so(vector<int>&data,int l,int r)
    {
        if(l>=r)return 0;
        int mid=(l+r)>>1,result=(so(data,l,mid)+so(data,mid+1,r))%1000000007;
        int le=mid,ri=r;
        vector<int>d;
        while(le>=l&&ri>=mid+1)
        {
            if(data[le]>data[ri])result+=ri-mid,d.push_back(data[le--]);
            else d.push_back(data[ri--]);
        }
        for(;le>=l;le--)d.push_back(data[le]);
        for(;ri>=mid;ri--)d.push_back(data[ri]);
        for(int i=l;i<=r;i++)
        data[i]=d[r-i];
        return result%1000000007;
    }
    int InversePairs(vector<int> data) {
        return so(data,0,data.size()-1);
    }
};