全RE,求调

P1908 逆序对

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了 需要离散化 我也是刚反应过来


|