社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...