树状数组
查看原帖
树状数组
1250563
Celestinefly楼主2024/4/20 22:22
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=5e5+10;
int n;
int a[N],s[N],rp[N];
int lowbit(int x){
    return x&(-x);
}

void change(int k,int x){
    while(x<=n){
        s[x]+=k;
        x+=lowbit(x);
    }
}

int query(int x){
    int t=0;
    while(x>=1){
        t+=s[x];
        x-=lowbit(x);
    }
    return t;
}

bool cmp(int x,int y){
    if(a[x]==a[y]) return x>y;
    return a[x]>a[y];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        rp[i]=i;
    }
    int sum=0;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        change(1,rp[i]);
        sum+=query(rp[i]-1);
    }
    printf("%d\n",sum);
    return 0;
}

我这个连案例都过不了,谁能帮我看看啊

2024/4/20 22:22
加载中...