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

#include <vector>
class Solution {
public:
    //利用归并排序
    long long ans;
    vector<int> a;
    vector<int>t;
    void merge(int l,int r,int mid){
        int i=l,j=mid,p=l;
        cout<<l<<r<<" ";
        while(i<mid&&j<=r){
            if(a[i]<=a[j]) t[p++]=a[i++];
            else {
                t[p++]=a[j++];
                ans+=(mid-i);//只在归并排序上额外加上这一句
            }
        }
        while(i<mid) t[p++]=a[i++];
        while(j<=r) t[p++]=a[j++];
        p=l;
        while(p!=r+1){
            a[p]=t[p];
            p++;
        }
    }
    void mergeSort(int l,int r){
        if(l<r)
        {
            int mid=(l+r)/2;
            mergeSort(l, mid);
            mergeSort(mid+1, r);
            merge(l,r,mid+1);
        }
    }
    int InversePairs(vector<int> data) {
        this->ans=0;
        this->a=data;
        this->t=data;
        mergeSort(0,data.size()-1);
        return ans%1000000007;
    }
};