题目描述

求逆序对

C++ 代码

#include[HTML_REMOVED]
using namespace std;
const int N=100000;
typedef long long LL;
int n,num[N],tmp[N];
LL mergeSort(int q[],int l,int r){
if(l>=r) return 0;
int mid=l+r >>1;
// 在中点左边和右边逆序对的数量和
LL res=mergeSort(q,l,mid)+mergeSort(q,mid+1,r);
int i=l,k=0,j=mid+1;
//第三步 两个有序对里面求逆序对的数量
while(i<=mid&&j<=r){
if(q[i]>q[j]) {
tmp[k]=q[j];
res+=mid-i+1; //i后面的值都肯定大于j，因为归并是将两个有序序列合并的过程，这里要统计在两边的情况//的逆序对
}else tmp[k]=q[i];

 }
 //扫尾
 while(i<=mid) tmp[k++]=q[i++];
 while(j<=r) tmp[k++]=q[j++];
 //将tmp数组的值转移回原数组
 for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
  return res;

}
int main(){
cin>>n;
for(int i=0;i<n;i++) scanf(“%d”,&num[i]);
cout<<mergeSort(num,0,n-1);
return 0;
}