suxiaozhou @ 2024-01-30 21:14:35
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[500100],b[500100],c[500100],n,m;
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for (;x<=m;x+=lowbit(x)){
c[x]+=y;
}
}
int query(int x){
int cnt=0;
for (int i=x;i;i-=lowbit(i)){
cnt+=c[i];
}
return cnt;
}
signed main(){
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
long long ans=0;
for (int i=n;i;i--){
int k=lower_bound(b+1,b+1+n,a[i])-b;
ans+=query(k-1);
add(k,1);
}
cout<<ans<<endl;
return 0;
}
谢谢大佬!!
by Terrible @ 2024-01-30 21:21:31
@suxiaozhou
int k=lower_bound(b+1,b+1+m,a[i])-b;
n
改 m
。
by suxiaozhou @ 2024-01-30 21:58:00
谢谢大佬!!改好了!已AC!!