Splay 板子

OI wiki 代码害人不浅。

#include<bits/stdc++.h>
#define il inline 
using namespace std;
il int read()
{
	int xr=0,F=1; char cr=getchar();
	while(cr<'0'||cr>'9') {if(cr=='-') F=-1;cr=getchar();}
	while(cr>='0'&&cr<='9')
		xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
	return xr*F;
}
const int N=1e5+5;
struct tree{
	int s[2],siz,fa,key;
	tree(){s[0]=s[1]=siz=fa=key=0;}
}tr[N];
#define ls(x) tr[(x)].s[0]
#define rs(x) tr[(x)].s[1] 
int rt,idx;
il int add(int key) {tr[++idx].key=key,tr[idx].siz=1;return idx;}
il void maintain(int x) {tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;}
il void clear(int x) {ls(x)=rs(x)=tr[x].siz=tr[x].fa=tr[x].key=0;}
il bool get(int x) {return x==tr[tr[x].fa].s[1];}
il void rotate(int x)
{
	int y=tr[x].fa,z=tr[y].fa; int chk=get(x);
	if(tr[x].s[chk^1]) tr[tr[x].s[chk^1]].fa=y;
	tr[y].s[chk]=tr[x].s[chk^1];
	tr[x].s[chk^1]=y,tr[y].fa=x,tr[x].fa=z;
	if(z) tr[z].s[y==tr[z].s[1]]=x;
	maintain(y),maintain(x);
}
il void splay(int x)
{
	for(int f=tr[x].fa;f=tr[x].fa,f;rotate(x))
		if(tr[f].fa) rotate(get(f)==get(x)?f:x);
	rt=x;
}
il void ins(int key)
{
	int now=rt,f=0;
	while(now) f=now,now=tr[now].s[key>tr[now].key];
	now=add(key),tr[now].fa=f,tr[f].s[key>tr[f].key]=now;
	splay(now);
}
il void del(int key)
{
	int now=rt;
	while(tr[now].key!=key&&now) now=tr[now].s[key>tr[now].key];
	if(!now) return; 
	splay(now);int cur=ls(now);
	if(!cur) {rt=rs(now),tr[rs(now)].fa=0,clear(now);return;}
	while(rs(cur)) cur=rs(cur);
	rs(cur)=rs(now),tr[rs(now)].fa=cur,tr[ls(now)].fa=0,clear(now);
	maintain(cur),splay(cur);
}
il int rnk(int key)
{
	int res=1,now=rt,p;
	while(now)
		if(p=now,tr[now].key<key) res+=tr[ls(now)].siz+1,now=rs(now);
		else now=ls(now);
	splay(p);
	return res;
}
il int kth(int rk)
{
	int now=rt;
	while(now)
		if(tr[ls(now)].siz+1>rk) now=ls(now);
		else if(tr[ls(now)].siz+1==rk) break;
		else rk-=tr[ls(now)].siz+1,now=rs(now);
	splay(now);return tr[now].key;
}
il int pre(int key)
{
	int now=rt,ans=0,p;
	while(now)
		if(p=now,tr[now].key>=key) now=ls(now);
		else ans=tr[now].key,now=rs(now);
	splay(p); return ans;
}
il int nxt(int key)
{
	int now=rt,ans=0,p;
	while(now)
		if(p=now,tr[now].key<=key) now=rs(now);
		else ans=tr[now].key,now=ls(now);
	splay(p);return ans;
}
int main()
{
	int n=read();
	while(n--)
	{
		int op=read(),x=read();
//		if(op==2) debug(rt);
//		cerr<<op<<" "<<x<<endl;
		if(op==1) ins(x);
		else if(op==2) del(x);
		else if(op==3) printf("%d\n",rnk(x));
		else if(op==4) printf("%d\n",kth(x));
		else if(op==5) printf("%d\n",pre(x));
		else printf("%d\n",nxt(x));
//		if(op==2) debug(rt);
	}
	return 0;
}