http://www.zybbs.org/JudgeOnline/problem.php?id=1861

一开始写这道题的时候总觉得自己的Splay模板的Join和Remove操作有问题……然后弄了半天各种WA囧，最后发现是题中的Insert操作交换时没更新指针……不过原来的Splay模板还真的有问题……Remove后可能存在未update的节点……改好就A了……

Query：Rank第i个节点后输出此节点的编号

Ask：Splay编号i对应节点后输出根的左子树的大小

Top/Bottom：删除编号i对应节点，找到最左/右边的节点，将编号i对应节点插入。（我的Splay在n=1时会出错，所以我特判了下）

Insert：0就不变，否则找到编号i对应节点的前/后继，与编号i对应节点交换，注意交换后的指针更新！

PS：Remove神马操作之后全部splay或者update一下……避免节点未update……

由于我感嚼我的Splay模板还有问题……所以就不挂Splay模板了囧……

#include <stdio.h>
#include <string.h>
#define maxn 80000
typedef struct _Splay{struct _Splay *c[2],*f;int s,v;}Splay,*PSplay;
Splay null,st[maxn],*pt[maxn],*r;
int n,m;
char str[2000000],*p=str;
inline PSplay update(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+1,x;}
inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		update((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x){
	if(x==&null||x->f==&null)return update(x);
	for(;x->f!=&null;rot(x))if(x->f->f!=&null)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return update(x);
}inline PSplay Join(PSplay r1,PSplay r2){
	if(r1==&null)return r2;if(r2==&null)return r1;
	while(r1->c[1]!=&null)r1=r1->c[1];
	return update((splay(r1)->c[1]=splay(r2))->f=r1);
}inline PSplay Remove(PSplay x){
	PSplay t=x->f;_Bool c=t->c[1]==x;
	if(x->c[0]==&null&&x->c[1]==&null)x->f->c[c]=&null;
	else if((x->c[0]->f=x->c[1]->f=&null)!=((t=Join(x->c[0],x->c[1]))->f=x->f))x->f->c[c]=t;
	return splay(t);
}inline PSplay Rank(PSplay r,int x){
	_Bool c;
	if(x<=0||r->s<x)return &null;
	for(;;r=r->c[c])if(x==r->c[0]->s+1)return splay(r);else if(c=x>r->c[0]->s)x-=r->c[0]->s+1;
}inline getint(){
	int re=0;_Bool k;
	while(*p!='-'&&(*p<'0'||*p>'9'))p++;
	for((k=*p=='-')&&++p;*p>='0'&&*p<='9';)re=re*10+*p++-48;
	return k?-re:re;
}main(){
	int i,c;fread(str,1,2000000,stdin);
	r=null.f=null.c[0]=null.c[1]=&null;
	for(i=n=getint(),m=getint();i--;(r=st+i)->c[1]=&null){
		(pt[st[i].v=getint()-1]=st+i)->s=r->s+1;
		if((st[i].c[0]=r)!=&null)r->f=st+i;
	}for(st[0].f=&null;m--;){
		while(*p<'A'||*p>'Z')p++;
		if(*p=='Q')printf("%d\n",(r=Rank(r,getint()))->v+1);
		else if(*p=='A')printf("%d\n",(r=splay(pt[getint()-1]))->c[0]->s);
		else if(*p=='I'){
			if(!(i=getint()-1,c=getint()))continue;
			for(r=splay(pt[i])->c[!(c=c!=1)];r->c[c]!=&null;r=r->c[c]);
			c=r->v;pt[pt[r->v=i]->v=c]=pt[i];pt[i]=r;r=splay(r);
		}else if(n!=1){
			for(c=*p=='B',r=Remove(pt[i=getint()-1]);r->c[c]!=&null;r=r->c[c]);
			((pt[i]->f=r)->c[c]=pt[i])->s=1;pt[i]->c[0]=pt[i]->c[1]=&null;
			r=splay(pt[i]);
		}
	}return 0;
}

• inline
• block