记录编号	600114	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.352 s
提交时间	2025-04-15 21:43:20	内存使用	4.11 MiB

#include<bits/stdc++.h>
#define maxn 100010
#define inf 1000000000
using namespace std;
int sum;
struct node{
	int l,r;
	int z,c;
	int si,s;
}a[maxn];
int _new(int x){
	a[++sum].z=x;a[sum].s=rand();
	a[sum].si=a[sum].c=1;
	return sum;
}
void update(int p){
	a[p].si=a[a[p].l].si+a[p].c+a[a[p].r].si;
	return;
}
void build(int &ro){
	ro=_new(-inf);a[ro].r=_new(inf);
	update(ro);
	return;
}
void zig(int &p){
	int q=a[p].l;
	a[p].l=a[q].r;a[q].r=p;p=q;
	update(a[p].r);update(p);
	return;
}
void zag(int &p){
	int q=a[p].r;
	a[p].r=a[q].l;a[q].l=p;p=q;
	update(a[p].l);update(p);
	return;
}
void insert(int &p,int x){
	if(a[p].z==x){
		a[p].c++;update(p);
		return;
	}
	if(p==0){
		p=_new(x);
		return;
	}
	if(x<a[p].z){
		insert(a[p].l,x);
		if(a[a[p].l].s>a[p].s)zig(p);
	}
	else{
		insert(a[p].r,x);
		if(a[a[p].r].s>a[p].s)zag(p);
	}
	update(p);
	return;
}
void remove(int &p,int x){
	if(a[p].z==x){
		if(a[p].c==1){
			if(a[p].l||a[p].r){
				if(a[p].r==0||a[a[p].l].s>a[a[p].r].s){
					zig(p);
					remove(a[p].r,x);
				}
				else{
					zag(p);
					remove(a[p].l,x);
				}
				update(p);
			}
			else p=0;
			return;
		}
		else{
			a[p].c--;
			update(p);
		}
		return;
	}
	if(x<a[p].z)remove(a[p].l,x);
	else remove(a[p].r,x);
	update(p);
	return;
}
int getrank(int p,int x){
	if(p==0)return 0;
	if(a[p].z==x)return a[a[p].l].si;
	if(a[p].z>x)return getrank(a[p].l,x);
	return a[a[p].l].si+a[p].c+getrank(a[p].r,x);
}
int getz(int p,int x){
	if(x>a[p].si)return inf;
	if(a[a[p].l].si>=x)return getz(a[p].l,x);
	if(a[a[p].l].si+a[p].c>=x)return a[p].z;
	return getz(a[p].r,x-a[a[p].l].si-a[p].c);
}
int getpre(int ro,int x){
	int ans=1,p=ro;
	while(p){
		if(a[p].z<x&&a[p].z>a[ans].z)ans=p;
		if(a[p].z==x){
			if(a[p].l)p=a[p].l;
			while(a[p].r)p=a[p].r;
			if(a[p].z<x&&a[p].z>a[ans].z)ans=p;
			break;
		}
		if(x<a[p].z)p=a[p].l;
		else p=a[p].r;
	}
	return a[ans].z;
}
int getnext(int ro,int x){
	int ans=2,p=ro;
	while(p){
		if(a[p].z>x&&a[p].z<a[ans].z)ans=p;
		if(a[p].z==x){
			if(a[p].r)p=a[p].r;
			while(a[p].l)p=a[p].l;
			if(a[p].z>x&&a[p].z<a[ans].z)ans=p;
			break;
		}
		if(x<a[p].z)p=a[p].l;
		else p=a[p].r;
	}
	return a[ans].z;
}
int root,m,a1,a2;
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	build(root);
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&a1,&a2);
		if(a1==1)insert(root,a2);
		if(a1==2)remove(root,a2);
		if(a1==3)printf("%d\n",getrank(root,a2));
		if(a1==4)printf("%d\n",getz(root,a2+1));
		if(a1==5)printf("%d\n",getpre(root,a2));
		if(a1==6)printf("%d\n",getnext(root,a2));
	}
	return 0;
}