题解：P17233 [Algo Beat Contest 017 B] 线性筛

tianye1010 · 2026-08-10 20:29:09 · 题解

（鼓励大炮打蚊子。）

来发一篇 AVL 平衡树的题解，（不会戳这里）。

直接模拟题意，用平衡树维护下标的顺序，先按下标插入，然后按排名删除即可。

时间复杂度 O(n \log n)。

但是有点小常数，卡卡常就行。

#include<bits/stdc++.h>
#define ll long long
#define p1 first
#define p2 second
#define pll pair<ll,ll>
using namespace std;
const ll N=1e6+5;
ll idx,root,n,ans;
ll b[1000];
struct st{
    ll l,r,val,siz,h,a;
};
st t[N];
ll nt(ll val,ll a){//新建节点
    t[++idx]={0,0,val,1,0,a};
    return idx;
}
ll bf(ll now){//树高平衡因子
    return t[t[now].l].h-t[t[now].r].h;
}
void pushup(ll now){//更新
    t[now].siz=t[t[now].l].siz+t[t[now].r].siz+1;
    t[now].h=max(t[t[now].l].h,t[t[now].r].h)+1;
}
void lt(ll &now){//左旋
    ll y=t[now].r;
    t[now].r=t[y].l;
    t[y].l=now;
    now=y;
    pushup(t[now].l);
    pushup(now);
}
void rt(ll &now){//右旋
    ll y=t[now].l;
    t[now].l=t[y].r;
    t[y].r=now;
    now=y;
    pushup(t[now].r);
    pushup(now);
}
void ch(ll &now){//维护树高
    ll s=bf(now);
    if(s>1){
        ll ss=bf(t[now].l);
        if(ss>0)rt(now);
        else lt(t[now].l),rt(now);
    }else if(s<-1){
        ll ss=bf(t[now].r);
        if(ss<0)lt(now);
        else rt(t[now].r),lt(now);
    }else if(now)pushup(now);
}
void ins(ll &now,ll val,ll a){//插入（val是下标，a是值）
    if(!now)now=nt(val,a);
    else if(t[now].val<=val)ins(t[now].r,val,a);
    else ins(t[now].l,val,a);
    ch(now);
}
void del(ll &now,ll val){//按排名删除并输出a值
    if(t[t[now].l].siz+1==val){
        if(!t[now].r||!t[now].l){
            cout<<t[now].a<<' ';
            now=t[now].l^t[now].r;
        }
        else if(bf(now)<0)rt(now),del(now,val);
        else lt(now),del(now,val);
    }
    else if(t[t[now].l].siz>=val)del(t[now].l,val);
    else del(t[now].r,val-t[t[now].l].siz-1);
    ch(now);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++){//插入
        ll x;
        cin>>x;
        ins(root,i,x);
    }
    for(int i=1;i<=101;i++){//预处理立方数
        b[i]=i*i*i;
    }
    ll cnt=0;
    while(cnt<n){//先求出操作次数
        ans++;
        ll cc=cnt;
        for(int i=1;b[i]<=n-cc;i++){//n-cc表示在该次操作中要减去已经被删除的元素
            cnt++;
        }
    }
    cnt=0;
    cout<<ans;
    while(cnt<n){//边删除，边输出
        cout<<"\n";
        ll cc=cnt;
        for(int i=1;b[i]<=n-cc;i++){
            del(root,b[i]-(i-1));//因为删除后下标会偏移，所以要减去偏移量
            cnt++;
        }
    }
    return 0;
}

建议使用 c++98 提交，因为跑的比较快。