题解 | #归并——数组中的逆序对#

#include <vector>
class Solution {
public:
    void merge_sort(vector<int>& data,int l,int r,int &ans){
        if(l>=r){
            return;
        }
        int mid = (l+r)/2;
        merge_sort(data,l,mid,ans);
        merge_sort(data,mid+1,r,ans);
        int i = l,j=mid+1,k=0;
        vector<int> temp(r-l+1);
        while (i<=mid && j<=r) {
            if(data[i] <= data[j]){
                temp[k++] = data[i++];
            }else {
                ans +=(mid - i+1); 
                ans = ans%1000000007;
                temp[k++] = data[j++];
            }
        }
        while (i<=mid) {
            temp[k++] = data[i++];
        }
        while (j<=r) {
            temp[k++] =  data[j++];
        }
        i = l;k = 0;
        while (l<=r) {
            data[l++] = temp[k++];
        }
        return;
    }
    int InversePairs(vector<int> data) {
        int ans = 0;
        int n = data.size();
        if(n < 2)
            return ans;
        merge_sort(data,  0, n-1, ans);
        return ans;
    }
};