【BZOJ1861】书架

    裸的Splay。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=80010;

struct Splay_Tree
{
	struct Node
	{
		Node *c[2],*p;
		int id;
		int size;
		bool w() {return p->c[1]==this;}
	}*Null,*root,*ID[maxn];
	int n;

	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x) {if (x==Null) return;x->size=ls->size+rs->size+1;}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		if (p==root) root=x;
		p->p->c[p->w()]=x;x->c[!w]->p=p;
		x->p=p->p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x,Node *top)
	{
		if (x==Null) return;
		while (x->p!=top)
		{
			if (x->p->p==top) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	Node* Select(int kth)
	{
		Node *x=root;
		while (kth)
		{
			int lsz=ls->size;
			if (lsz+1==kth) return x;
			if (lsz>=kth) x=ls;else x=rs,kth-=lsz+1;
		}
	}

	void Delete(Node *x)
	{
		x->p->c[x->w()]=Null;
		Splay(x->p,Null);
		x->p=Null;
	}

	void Delete(int x)
	{
		if (x==1) Splay(Select(2),Null),Delete(Select(1));
		else if (x==n) Splay(Select(n-1),Null),Delete(Select(n));
		else Splay(Select(x-1),Null),Splay(Select(x+1),root),Delete(Select(x));
		n--;
	}

	void Insert(int x,int pos)
	{
		if (root==Null) root=ID[x];
		else if (pos==1) Splay(Select(1),Null),root->c[0]=ID[x],ID[x]->p=root,Splay(ID[x],Null);
		else if (pos==n+1) Splay(Select(n),Null),root->c[1]=ID[x],ID[x]->p=root,Splay(ID[x],Null);
		else Splay(Select(pos-1),Null),Splay(Select(pos),root),root->c[1]->c[0]=ID[x],ID[x]->p=root->c[1],Splay(ID[x],Null);
		n++;
	}

	void Init(int _n)
	{
		n=0;
		for (int i=0;i<=_n;i++) ID[i]=new Node;
		Null=ID[0];
		for (int i=0;i<=_n;i++) ID[i]->c[0]=ID[i]->c[1]=ID[i]->p=Null,ID[i]->size=1,ID[i]->id=i;
		Null->size=0;
		root=Null;
	}

	void Change(int x,int pos)
	{
		Delete(Rank(x));
		Insert(x,pos);
	}

	int KBook(int x)
	{
		Splay(Select(x),Null);
		return root->id;
	}

	int Rank(int x)
	{
		Splay(ID[x],Null);
		return root->c[0]->size+1;
	}
}T;

char ctr[20];

int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	T.Init(n);
	for (int i=1,x;i<=n;i++) scanf("%d",&x),T.Insert(x,i);
	while (m--)
	{
		scanf("%s",ctr);
		int x,y;
		if (ctr[0]=='T') scanf("%d",&x),T.Change(x,1);
		if (ctr[0]=='B') scanf("%d",&x),T.Change(x,n);
		if (ctr[0]=='I') scanf("%d%d",&x,&y),T.Change(x,T.Rank(x)+y);
		if (ctr[0]=='Q') scanf("%d",&x),printf("%d\n",T.KBook(x));
		if (ctr[0]=='A') scanf("%d",&x),printf("%d\n",T.Rank(x)-1);
	}
	return 0;
}