MLE 8个

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define max(a,b) (a>b?a:b)
#define re register int
using namespace std;
inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}

const int N=1e5+5,INF=1e8+7;
struct tq
{
	int v,size,l,r,pri,num;
}q[N];
int n,cnt,opt,m,R;
inline void zig (int &x)//右旋,根往右,左儿子当爹 
{
	re tmp=q[x].l;
	q[x].l=q[tmp].r;
	q[tmp].r=x;
	x=tmp;
}

inline void zag (int &x)//左旋,根往左,右儿子当爹
{
	re tmp=q[x].r;
	q[x].r=q[tmp].l;
	q[tmp].l=x;
	x=tmp;
}

inline void upd(int x)
{
	q[x].size=q[q[x].l].size+q[q[x].r].size+q[x].num;
}

inline void add(int &x,int d)
{
	if(!x)
	{
		x=++cnt;
		q[x].v=d;
		q[x].size=1;
		q[x].pri=rand();
		q[x].num=1;
		return;
	}
	if(q[x].v==d)
	{
		++q[x].num;
		++q[x].size;
		return;
	}
	if(d<q[x].v)
	{
		add(q[x].l,d);
		if(q[q[x].l].pri<q[x].pri)
			zig(x);		
	}
	else
	{
		add(q[x].r,d);	
		if(q[q[x].r].pri<q[x].pri)
			zag(x);		
	}
	upd(x);
}

inline void del(int &x,int d)
{
	if(q[x].v==d)
	{
		if(!q[x].l&&!q[x].r)
		{
			--q[x].num;
			if(!q[x].num)
				x=0;
			return;
		}		
		else if(q[x].l&&!q[x].r)
		{
			zag(x);
			del(q[x].r,d);
		}
		else if(!q[x].l&&q[x].r)
		{
			zig(x);
			del(q[x].l,d);			
		}
		else
		{
			if(q[q[x].l].pri<q[q[x].r].pri)
			{
				zig(x);	
				del(q[x].r,d);
			}	
			else
			{
				zag(x);
				del(q[x].l,d);
			}
		}
		upd(x);
	}
	else if(d<q[x].v)
	{
		del(q[x].l,d);
		upd(x);	
	}
	else 
	{
		del(q[x].r,d);
		upd(x);
	}
}

inline int rank(int x,int d)
{
	if(!x)
		return 0;
	if(d==q[x].v)
		return q[q[x].l].size+1;
	else if(d<q[x].v)
		return rank(q[x].l,d);	
	else 
		return rank(q[x].r,d)+q[x].num+q[q[x].l].size;
}

inline int query(int x,int d)
{
	if(d>=q[q[x].l].size+1&&d<=q[q[x].l].size+q[x].num)
		return q[x].v;
	else if(d<=q[q[x].l].size)	
		return query(q[x].l,d);
	else return query(q[x].r,d-q[q[x].l].size-q[x].num);
}

inline int pre(int x,int d)
{
	if(!x)
		return -INF; 
	if(q[x].v>=d)
		return pre(q[x].l,d);
	else return max(pre(q[x].r,d),q[x].v);
}

inline int nex(int x,int d)
{
	if(!x)
		return INF; 
	if(q[x].v<=d)
		return nex(q[x].r,d);
	else return min(nex(q[x].l,d),q[x].v);
}
int main()
{
	n=read();
	for(re i=1;i<=n;++i)
	{
		opt=read();
		m=read();
		if(opt==1)	add(R,m);		
		else if(opt==2)	del(R,m);
		else if(opt==3)	printf("%d\n",rank(R,m));
		else if(opt==4)	printf("%d\n",query(R,m));
		else if(opt==5)	printf("%d\n",pre(R,m));
		else if(opt==6)	printf("%d\n",nex(R,m));		
	}
	
	
}