在线求助,急
查看原帖
在线求助,急
1081418
Echoyang楼主2025/7/2 15:24

rt,代码中每一个数左右比它大的数计算有误,能不能帮忙调一下

#include<bits/stdc++.h>
using namespace std;
#define clean(X) memset(X,0,sizeof(X))
long long lx[114514*2],rx[114514*2],c[114514*2],a[114514*2],sum1=0;
int n;
int lowbit(int x){
    return x&-x;
}
void add(int x,int y){
    while(x<=n){
        c[x]+=y;
        x=x+lowbit(x);
    }return ;
}
int ask(int x){
    int cnt=0;
    while(x){
        cnt+=c[x];
        x=x-lowbit(x);
    }return cnt;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]++;
    }
    for(int i=1;i<=n;i++){
        lx[i]=i-1-ask(a[i]);
        add(a[i],1);
    }
    clean(c);
    for(int i=n;i>=1;i--){
        rx[i]=n-i-ask(a[i]);
        add(a[i],1);
    }
    for(int i=1;i<=n;i++){
        if(max(lx[i],rx[i])>min(lx[i],rx[i])<<1){
            sum1++;
            // cout<<lx[i]<<'l'<<rx[i]<<'r'<<i<<'\n';
        }
    }
    cout<<sum1;
}
2025/7/2 15:24
加载中...