题目如下

思路与代码

其实就是归并排序的一个变形，中间加了个判断。即，
//如果前面的元素小于后面的不能构成逆序对
//如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对

class Solution {
public:
    void merge_sort(vector<int> &first,vector<int> &second,int left,int right,int &res)
    {
        if(left>=right)
        {
            return ;
        }
        int mid=left+(right-left)/2;
        merge_sort(first,second,left,mid,res);
        merge_sort(first,second,mid+1,right,res);
        merge(first,second,left,mid,right,res);
    }
    void merge(vector<int> &first,vector<int> &second,int left,int mid,int right,int &res)
    {
        int l=left,m=mid+1,k=0;
        while(l<=mid&&m<=right)
        {
            if(first[l]>first[m])
            {
                res+=mid-l+1;
                res=res%1000000007;
                second[k]=first[m];
                k++,m++;
            }
            else
            {
                second[k]=first[l];
                l++,k++;
            }
        }
        while(l<=mid)
        {
            second[k]=first[l];
            k++,l++;
        }
        while(m<=right)
        {
            second[k]=first[m];
            k++,m++;
        }
        for(k=0,l=left;l<=right;l++,k++)
        {
            first[l]=second[k];
        }
    }
    int InversePairs(vector<int> data) {
        int result=0;
        vector<int> temp(data.size());
        merge_sort(data, temp,0,data.size()-1,result);
        return result;
    }
};