社区讨论

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 条回复,欢迎继续交流。

正在加载回复...