lyx0813 @ 2024-09-10 18:55:37
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[500100],c[500100];
int lowbit(int x){
return x&(-x);
}
void add(int x){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=1;
}
}
long long sum(int x){
long long ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
long long ans2;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans2+=sum(n)-sum(a[i]);
add(a[i]);
}
printf("%lld",ans2);
return 0;
}
by canduanqi @ 2024-09-10 20:27:56
a[i]取值有1e9 放进1e5的树状数组就RE了 需要离散化 我也是刚反应过来