社区讨论

萌新刚学oi,splay60写挂,大佬们帮忙看下吧。。

P3369【模板】普通平衡树参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7xbp37
此快照首次捕获于
2025/11/21 05:08
4 个月前
此快照最后确认于
2025/11/21 05:08
4 个月前
查看原帖
rt 吹泡泡:
CPP
#include<iostream>
#include<cstdio>
using namespace std;
long long read(){
    char ch=getchar();long long x=0,pos=1;
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return pos?x:-x;
}
const long long maxn=1000111;
long long n,fa[maxn],val[maxn],cnt[maxn],ch[maxn][3],sz[maxn],rt,tot;
inline long long get(long long u){
    return (ch[fa[u]][1]==u);
}
inline void push_up(long long u){
    sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+cnt[u];
}
inline void rotate(long long u){
    long long f=fa[u];long long g=fa[f];long long k=get(u);
    fa[u]=g;
     ch[g][get(f)]=u;
    fa[ch[u][k^1]]=f;
     ch[f][k]=ch[u][k^1];
    fa[f]=u;
     ch[u][k^1]=f;
     
    push_up(f);
    push_up(u); // ※※※ 
}
inline void splay(long long u,long long v){
    while(fa[u]!=v){
        long long f=fa[u];
        if(fa[f]!=v){
            rotate((get(f)==get(u)?f:u));
        }
        rotate(u);
    }
    if(!v) rt=u;
}
inline void insert(long long key){
    long long u=rt,p=0;
    while(u&&val[u]!=key){
        p=u;
        u=ch[u][key>val[u]];
    }
    if(u) ++cnt[u];
    else{
        u=++tot; 
        val[u]=key;
        if(p){
            ch[p][key>val[p]]=u;
        }
        sz[u]=1;
        fa[u]=p;
        cnt[u]=1;
        ch[u][0]=ch[u][1]=0;
    } 
    splay(u,0);
}
inline void find(long long key){
    long long u=rt;
    while(val[u]!=key&&ch[u][key>val[u]]) u=ch[u][key>val[u]];
    splay(u,0);
}
inline long long rnk(long long key){
    find(key);
    return sz[ch[rt][0]];//有-inf这个点,不用加一 
}
inline long long kth(long long k){
    ++k;// -inf
    long long u=rt;
    while(1926){
        if(sz[ch[u][0]]+cnt[u]<k) k-=(sz[ch[u][0]]+cnt[u]),u=ch[u][1];
        else if(k<=sz[ch[u][0]]) u=ch[u][0];
        else return val[u]; 
    }
    //k < sz[ch[u][0]]: 在左子树中
    //sz[ch[u][0]] < k <= sz[ch[u][0]]+cnt[u] 为当前值
    //否则是右子树中 
}
inline long long pre(long long key){
    find(key);
    if(val[rt]<key) return rt;
    long long u=ch[rt][0];
    while(ch[u][1]){
        u=ch[u][1];
    }
    return u;
} 
inline long long suc(long long key){
    find(key);
    if(val[rt]>key) return rt;
    long long u=ch[rt][1];
    while(ch[u][0]){
        u=ch[u][0];
    }
    return u;
}
inline void del(long long key){
    long long pr=pre(key),su=suc(key);
    splay(pr,0);
    splay(su,pr);
    long long u=ch[su][0];
    //把key的前驱伸展到rt,后继伸展到rt的右儿子
    //那么key一定是后继的左儿子,而且没有儿子
    if(cnt[u]>1){
        cnt[u]--;
        splay(u,0);
    }else{
        ch[su][0]=0;
        splay(su,0);
        cnt[u]=0;
    } 
}
int main(){
    n=read();
    insert(-192608170);
    long long x,opt;
    for(long long i=1;i<=n;i++){
        opt=read();x=read();
        if(opt==1){
        	insert(x);
            continue;
        }
        if(opt==2){
        	del(x);
            continue;
        }
        if(opt==3){
        	printf("%lld\n",rnk(x));
            continue;
        }
        if(opt==4){
        	printf("%lld\n",kth(x));
            continue;
        }
        if(opt==5){
        	printf("%lld\n",val[pre(x)]);
            continue;
        }
        if(opt==6){
        	printf("%lld\n",val[suc(x)]);
            continue;
        }
    }
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...