看错误样例才能做出来的不赖皮题解（可学
原题链接：7962.逆序对
2025-10-04 13:58:30
发布于：上海
9阅读
0回复
0点赞
#include<iostream>
using namespace std;
int a[500005],b[500005];
long long n,ans=0;
void m(int l,int r){
if(l==r)return ;
int p=(l+r)/2,i=l,j=p+1,k=0;
m(l,p);
m(p+1,r);
while(i<=p&&j<=r){
if(a[i]<=a[j]){
b[k]=a[i];
k++;
i++;
}
else{
b[k]=a[j];
k++;
j++;
ans+=(p-i)+1;
}
}
if(i<=p){
for(;i<=p;i++){
b[k]=a[i];
k++;
}
}
else{
for(;j<=r;j++){
b[k]=a[j];
k++;
}
}
for(int x=l;x<=r;x++)a[x]=b[x-l];
}
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
m(0,n-1);
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个