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

class Solution {
private:
    static constexpr long long mod=1e9+7;
public:
    //利用归并排序解决问题
    int InversePairs(vector<int> data) {
        int ret=0;
        vector<int> temp(data.size());
        merge_sort__(data,temp,0,(int)data.size()-1,ret);
        return ret;
    }

    void merge_sort__(vector<int>& arr,vector<int>& temp,int l,int r,int& ret){
        if(l>=r){
            return;
        }
        int mid=l+((r-l)>>1);
        merge_sort__(arr,temp,l,mid,ret);
        merge_sort__(arr,temp,mid+1,r,ret);
        merge__(arr,temp,l,mid,r,ret);
    }
    void merge__(vector<int>& arr,vector<int>& temp,int l,int mid,int r,int& ret){
        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){
            if(arr[i]>arr[j]){
                temp[k++]=arr[j++];
                ret+=(mid-i+1);
                ret%=mod;
            }else{
                temp[k++]=arr[i++];
            }
        }
        while(i<=mid){
            temp[k++]=arr[i++];
        }
        while(j<=r){
            temp[k++]=arr[j++];
        }
        for(k=0,i=l;i<=r;++i,k++){
            arr[i]=temp[k];
        }
    }
};