AcWing 788. 逆序对的数量
原题链接
简单
作者:
白小黑
,
2023-11-14 13:59:11
,
所有人可见
,
阅读 53
时间复杂度o(log(n))
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010;
int a[N],t[N],n;
long long dfs(int a[],int left,int right){
if(left>=right) return 0;
int mid=(left+right)>>1;
long long res=dfs(a,left,mid)+dfs(a,mid+1,right);
int i=left,j=mid+1,k=0;
while(i<=mid&&j<=right){
//用1次计算代替了n次计算
if(a[i]>a[j]){
res+=mid-i+1;
t[k++]=a[j++];
}else{
t[k++]=a[i++];
}
}
while(i<=mid) t[k++]=a[i++];
while(j<=right) t[k++]=a[j++];
for(int i=left,j=0;i<=right;i++){
a[i]=t[j++];
}
return res;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
//传入数组名是操作同一个数组
cout<<dfs(a,0,n-1);
return 0;
}