为何只有35分,我测了数据是对的,求助

P1908 逆序对

spacecraft__int @ 2021-12-30 19:57:26

#include<bits/stdc++.h>
using namespace std;
int n,m;
int lb(int x){return x&-x;}
long long a[5000005];
int tr[5000005];
int b[5000005],ans;
void add(int x){
    while(x<=n){
        tr[x]++;
        x+=lb(x);
    }
    return;
}
int sum(int x){
    int s=0;
    while(x>0){
        s+=tr[x];
        x-=lb(x);
    }
    return s;
}
bool cmp(int x,int y){
     return a[x]>a[y];
}
int main(){
//  freopen("P1908_6.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        b[i]=i;
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++) add(b[i]),ans+=sum(b[i]-1);
    printf("%d",ans);
    return 0;
}

by OldVagrant @ 2021-12-30 20:17:43

您这求的是正序对对数,逆序对的话下面那个for循环应该倒序


by OldVagrant @ 2021-12-30 20:23:07

@spacecraft__int


by spacecraft__int @ 2022-01-04 16:07:59

谢谢!


|