rt

R143112625

#include <iostream>
#include <cstdio>
#include <cctype>
#define cd(x) tr[x].cd
#define fa(x) tr[x].fa
#define ls [0]
#define rs [1]
#define inf 10000001
using namespace std;
struct node
{
	int cd[2],fa,dat,cnt,sz;
}tr[100005];
int top,rut,n,tsk,u;
inline void read(int &x)
{
	char c=getchar();x=0;bool fl=false;
	while(!isdigit(c)) fl=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	x=(1-2*fl)*x;
}
int mkn(int k)
{
	tr[++top].dat=k;tr[top].cnt=tr[top].sz=1;
	return top;
}
void upd(int now)
{
	tr[now].sz=tr[cd(now)ls].sz+tr[cd(now)rs].sz+tr[now].cnt;
}
void lnk(int u,int v) //将v挂载到u下面 
{
	if(u) cd(u)[tr[u].dat<tr[v].dat]=v,upd(u);
	if(v) fa(v)=u,upd(v);
}
bool glr(int now)
{
	return cd(fa(now))[1]==now;
}
void rtt(int now)
{
	if(!fa(now)) return;
	bool dir=glr(now);int f=fa(now);
	lnk(fa(f),now);
	if(cd(now)[!dir]) lnk(f,cd(now)[!dir]);
	else cd(f)[dir]=0;
	lnk(now,f);
	upd(f);upd(now);upd(fa(f));
}
void spl(int now,int gol)
{
	for(int f=fa(now);f=fa(now),fa(f)^gol&&f^gol;rtt(now))
		if(fa(f)) rtt(glr(f)==glr(now)?f:now);
	if(fa(now)^gol) rtt(now);
	if(!gol) rut=now;
}
int kqry(int now,int k) //关于k的查询 
{
	int p=0;
	while(now)
	{
		if(tr[now].dat==k) return now;
		if(tr[now].dat<k&&tr[now].dat>tr[p].dat) p=now;
		now=cd(now)[tr[now].dat<k];
	}
	return p;
}
int rqry(int now,int k)
{
	if(tr[cd(now)ls].sz<k&&k<=tr[cd(now)ls].sz+tr[now].cnt) return now;
	if(tr[cd(now)ls].sz>=k) return rqry(cd(now)ls,k);
	else return rqry(cd(now)rs,k-tr[cd(now)ls].sz-tr[now].cnt);
}
void ins(int k)
{
	int x=kqry(rut,k);spl(x,0);
	int y=rqry(cd(x)rs,1);spl(y,x);
	if(tr[x].dat==k) tr[x].cnt++;
	else lnk(x,mkn(k)),lnk(top,y);upd(top);upd(x);
}
void del(int k)
{
	int x=kqry(rut,k);spl(x,0);
	int y=rqry(cd(x)rs,1);spl(y,x);
	if(tr[x].cnt>1) tr[x].cnt--,upd(x);
	else lnk(y,cd(x)ls);
}
int kqry(int k)
{
	spl(kqry(rut,u),0);
	return tr[cd(rut)ls].sz+(tr[rut].dat!=k);
}
int pre(int k)
{
	spl(kqry(rut,k),0);
	if(tr[rut].dat==k) return tr[rqry(cd(rut)ls,tr[cd(rut)ls].sz)].dat;
	else return tr[rut].dat;
}
int suf(int k)
{
	spl(kqry(rut,k),0);
	return tr[rqry(cd(rut)rs,1)].dat;
}
int main()
{
	lnk(rut=mkn(inf),mkn(-inf));
	upd(2);upd(1);tr[0].dat=-inf-1; //配合qry的查询 
	read(n);
	while(n--)
	{
		read(tsk);read(u);
		if(tsk==1) ins(u);
		else if(tsk==2) del(u);
		else if(tsk==3) printf("%d\n",kqry(u));
		else if(tsk==4) printf("%d\n",tr[rqry(rut,u+1)].dat);
		else if(tsk==5) printf("%d\n",pre(u));
		else if(tsk==6) printf("%d\n",suf(u));
	}
	return 0;
}