社区讨论
treap 52分 6~10WA 错在哪里呢??
P3369【模板】普通平衡树参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi7wr437
- 此快照首次捕获于
- 2025/11/21 04:52 4 个月前
- 此快照最后确认于
- 2025/11/21 04:52 4 个月前
CPP
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int INF = 0x3f3f3f3f;
int rt[100010][2],siz[100010],w[100010],pos[100010],cnt[100010];
int ans,n,root=1,tot=1,opt,x;
void pushup(int x) {
siz[x]=siz[rt[x][0]]+siz[rt[x][1]]+cnt[x];
}
void spin(int &t,int p) {
int y=rt[t][p];
rt[t][p]=rt[y][!p],rt[y][!p]=t,pushup(t),pushup(y),t=y;
}
void insert(int x,int &t) {
if(!t) {
t=++tot,cnt[t]=1,pos[t]=rand(),w[t]=x,siz[t]=1;
return ;
}
if(x==w[t]) cnt[t]++;
int p=x>w[t];
insert(x,rt[t][p]);
if(pos[t]>pos[rt[t][p]]) spin(t,p);
pushup(t);
}
void del(int x,int &t) {
if(!t) return ;
if(x==w[t]) {
if(cnt[t]>1) {
cnt[t]--,pushup(t);
return ;
}
if(!rt[t][0] || !rt[t][1]) {
t=rt[t][0]+rt[t][1];
return ;
}
int p=pos[rt[t][0]]>pos[rt[t][1]];
spin(t,p);
del(x,rt[t][p]);
}
int p=x>w[t];
del(x,rt[t][p]);
pushup(t);
}
int get_rank(int x,int t) {
if(!t) return 0;
if(x==w[t]) return siz[rt[t][0]]+1;
if(x<w[t]) return get_rank(x,rt[t][0]);
else return get_rank(x,rt[t][1])+siz[rt[t][0]]+cnt[t];
}
int get_val(int rank,int t) {
if(!t) return INF;
if(rank<=siz[rt[t][0]]) {
return get_val(rank,rt[t][0]);
} else if(rank<=siz[rt[t][0]]+cnt[t]) {
return w[t];
} else return get_val(rank-siz[rt[t][0]]-cnt[t],rt[t][1]);
}
int get_pre(int x,int t) {
if(!t) return -INF;
if(x>w[t]) return max(w[t],get_pre(x,rt[t][1]));
else return get_pre(x,rt[t][0]);
}
int get_next(int x,int t) {
if(!t) return INF;
if(x<w[t]) return min(w[t],get_next(x,rt[t][0]));
else return get_next(x,rt[t][1]);
}
int main() {
scanf("%d",&n);
while(n--) {
scanf("%d",&opt);
scanf("%d",&x);
if(opt==1) insert(x,root);
if(opt==2) del(x,root);
if(opt==3) printf("%d\n",get_rank(x,root));
if(opt==4) printf("%d\n",get_val(x,root));
if(opt==5) printf("%d\n",get_pre(x,root));
if(opt==6) printf("%d\n",get_next(x,root));
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...