55pts 树状数组求助!能看一眼吗?

P1908 逆序对

suxiaozhou @ 2024-01-30 21:14:35

11~19测试点WA了

代码:

#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;

nm


by suxiaozhou @ 2024-01-30 21:58:00

谢谢大佬!!改好了!已AC!!


|