逆序对
求助为毛样例是5,感觉代码也没太有问题
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,m,a[maxn],b[maxn],c[maxn];
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(;x<=n;x+=lowbit(x))c[x]+=y;
}
int ask(int x){
int y=0;
for(;x;x-=lowbit(x))y+=c[x];
return y;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+1);
b[i]=a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b;
long long ans=0;
for(int i=1;i<=n;i++){
add(a[i],1);
ans+=ask(m)-ask(a[i]);
}
cout<<ans;
return 0;
}