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

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{
	int ls,rs,val,s,siz,sum;
}tr[N];
int n,cnt,root;
void pushup(int p){
	tr[p].siz=tr[p].sum+tr[tr[p].ls].siz+tr[tr[p].rs].siz;
}
void lfr(int &p){
	int x=tr[p].rs;
	tr[p].rs=tr[tr[p].rs].ls;
	tr[x].ls=p;
	pushup(p);
	pushup(x);
	p=x;
}
void rtr(int &p){
	int x=tr[p].ls;
	tr[p].ls=tr[tr[p].ls].rs;
	tr[x].rs=p;
	pushup(p);
	pushup(x);
	p=x;
}
void insert(int x,int &p){
	if(x<tr[p].val){
		if(!tr[p].ls){
			tr[p].ls=++cnt;
			tr[cnt]={0,0,x,rand(),1,1};
		}
		else insert(x,tr[p].ls);
		if(tr[p].s>tr[tr[p].ls].s) rtr(p);
		pushup(p);		
		return;
	}
	if(x>tr[p].val){
		if(!tr[p].rs){
			tr[p].rs=++cnt;
			tr[cnt]={0,0,x,rand(),1,1};
		}
		else insert(x,tr[p].rs);
		if(tr[p].s>tr[tr[p].rs].s) lfr(p);
		pushup(p);		
		return;
	}
	if(x==tr[p].val){
		tr[p].sum++;
		pushup(p);
		return;
	}
}
void del(int x,int &p){
	if(x==tr[p].val){
		if(tr[p].sum>=2){
			tr[p].sum--;
			tr[p].siz--;
			return;
		}
		if(!tr[p].ls&&!tr[p].rs){
			tr[p]={0,0,0,0,0,0};
			p=0;
		}
		else if(tr[p].ls&&!tr[p].rs){
			int t=tr[p].ls;
			tr[p]={0,0,0,0,0,0};
			p=t;
			pushup(p);
		}
		else if(!tr[p].ls&&tr[p].rs){
			int t=tr[p].rs;
			tr[p]={0,0,0,0,0,0};
			p=t;
			pushup(p);
		}
		else if(tr[p].ls&&tr[p].rs){
			if(tr[tr[p].ls].s<tr[tr[p].rs].s){
				rtr(p);
				del(x,tr[p].rs);
				pushup(p);
			}
			else{
				lfr(p);
				del(x,tr[p].ls);
				pushup(p);
			}
		}
		return;
	}	
	if(x<tr[p].val){
		del(x,tr[p].ls);
		pushup(p);
		return;
	}
	if(x>tr[p].val){
		del(x,tr[p].rs);
		pushup(p);
		return;
	}
}
int qrank(int x,int p){
	if(p==0) return 0;
	if(x<tr[p].val){
		return qrank(x,tr[p].ls);
	}
	if(x>tr[p].val){
		return tr[tr[p].ls].siz+tr[p].sum+qrank(x,tr[p].rs);
	}
	if(x==tr[p].val){
		return tr[tr[p].ls].siz;
	}
}
int qrankx(int x,int p){
	if(x<=tr[tr[p].ls].siz){
		return qrankx(x,tr[p].ls);
	}
	if(x<=tr[tr[p].ls].siz+tr[p].sum){
		return tr[p].val;
	}
	if(x>tr[tr[p].ls].siz+tr[p].sum){
		return qrankx(x-(tr[tr[p].ls].siz+tr[p].sum),tr[p].rs);
	}
}
int qpre(int x){
	int ans=-2147483647;
	int p=root;
	while(1){
		if(p==0) break;
		if(x<=tr[p].val){
			p=tr[p].ls;
		}
		else{
			ans=tr[p].val;
			p=tr[p].rs;
		}
	}
	return ans;
}
int qnxt(int x){
	int ans=2147483647;
	int p=root;
	while(1){
//		if(x==887537) cout<<p<<"\n";
		if(p==0) break;
		if(x>=tr[p].val){
			p=tr[p].rs;
		}
		else{
			ans=tr[p].val;
			p=tr[p].ls;
		}
	}
	return ans;	
}
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	ios::sync_with_stdio(0);
	tr[++cnt]={0,0,2147483647,-1,0,0};
	root=cnt;
	cin>>n;
	for(int i=1;i<=n;i++){
		int op,x;
		cin>>op>>x;
		if(op==1)insert(x,root);
		if(op==2)del(x,root);
		if(op==3)cout<<qrank(x,root)+1<<"\n";
		if(op==4)cout<<qrankx(x,root)<<"\n";
		if(op==5)cout<<qpre(x)<<"\n";
		if(op==6)cout<<qnxt(x)<<"\n";
	}
	return 0;
}