public:
int temp[100005];
int InversePairs(vector<int> data) {
vector<int>copy;
for(int i=0;i<data.size();i++){//先保存下来
copy.push_back(data[i]);
}
return InversePairs1(data,0,data.size()-1);
}
int InversePairs1(vector<int> &data,int left,int right){
if(left==right)return 0;//递归到只有一个数
int mid=(left+right)/2;//先进行分治递归
//遍历左右子树,直至只有一个数
int leftInversePairs1=InversePairs1(data,left,mid);
int rightInversePairs1=InversePairs1(data,mid+1,right);
//左右子树都是有序的,逆序对在合并的过程中计算
int merge=merge_sort(data,left,mid,right);
return (leftInversePairs1+rightInversePairs1+merge)%1000000007;
}
int merge_sort(vector<int> &data,int left,int mid,int right){
for(int i=left;i<=right;i++){
temp[i] = data[i];//把所有值赋给临时数组,等下归并时要用
}
int i=left;
int j=mid+1;
int count=0;
//通过双指针比较 对两段数进行排序,并计算逆序对
for(int k=left;k<=right;k++){
if(mid+1==i){//左端先完
data[k]=temp[j];
j++;
}else if(j==right+1){
data[k]=temp[i];//右端先完
i++;
}else if(temp[i]<=temp[j]){
data[k]=temp[i];
i++;
}
else if(temp[i]>temp[j]){
data[k]=temp[j];
count+=(mid+1-i);
j++;
}
}
return count%1000000007;//不模不行
}
};