# ZJOI2006[书架]

``````/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年03月22日 星期五 15时46分12秒 *******************************/
#include <iostream>
#include <fstream>
#define rc(x) child[x][1]
#define lc(x) child[x][0]
using namespace std;
const int maxn = 100005;
int n,m,cnt,root,x,inc,rak;
int size[maxn],fa[maxn];
int child[maxn][2];
char s[10];
//{{{splay
inline void rotate (int x)
{
int f=fa[x],g=fa[f],c=rc(f)==x;
fa[child[x][!c]]=f,child[f][c]=child[x][!c];
fa[f]=x,child[x][!c]=f;
fa[x]=g;
if (g)	child[g][rc(g)==f]=x;
size[f]=size[lc(f)]+size[rc(f)]+1;
size[x]=size[lc(x)]+size[rc(x)]+1;
}
void splay (int x,int goal=0)
{
for (int f;(f=fa[x])!=goal;rotate(x))
if (fa[f]!=goal)	rotate((x==rc(f))==(f==rc(fa[f]))?f:x);
if (!goal)	root=x;
}
//}}}
//{{{kth
int kth (int res)//找到排名为x的数
{
int now=root;
while (true){
if (lc(now)&&res<=size[lc(now)])	now=lc(now);
else{
res-=size[lc(now)]+1;
if (res<=0)	return now;
now=rc(now);
}
}
}
//}}}
//{{{insert
void insert (int x,int k)//将x插入且使其排名为k,并把它转上来
{
if (k==1){  fa[x]=0, rc(x)=root,fa[root]=x, size[x]=size[root]+1, root=x; return;}
int f=kth(k-1);
splay(f);
++size[f];
rc(x)=rc(f);
fa[x]=f;
size[x]=size[rc(x)]+1;
fa[rc(x)]=x;
rc(f)=x;
splay(x);
}
//}}}
//{{{pre
int pre (bool t)//t==0 前驱 t==1 后继
{
int x=child[root][t];
t=!t;
while (child[x][t])	x=child[x][t];
return x;
}
//}}}
//{{{delet
void delet (int x)//删除x
{
splay(x);
int l=pre(0),r=pre(1);
if (!l&&!r)	size[x]=root=0;
else if (!l)	root=rc(x),fa[root]=rc(x)=size[x]=0;
else if (!r)	root=lc(x),fa[root]=lc(x)=size[x]=0;
else{
splay(l),splay(r,l);
lc(r)=0,--size[r],--size[l];
fa[x]=size[x]=0;
}
}
//}}}
//{{{Top
void Top (int x)
{
delet(x);
insert(x,1);
}
//}}}
//{{{Bottom
void Bottom (int x)
{
delet(x);
insert(x,n);
}
//}}}
{
splay(x);
cout<<size[lc(x)]<<endl;
}
//}}}
int main()
{
freopen("p2596.in","r",stdin);
freopen("p2596.out","w",stdout);
cin>>n>>m;
for (int i=1;i<=n;++i){
cin>>x;
insert(x,i);
}
for (int i=1;i<=m;++i){
cin>>(s+1)>>x;
if (s[1]=='I'){
cin>>inc;
splay(x);
rak=size[lc(x)]+1;
delet(x);
insert(x,rak+inc);
}
else if (s[1]=='Q')	cout<<kth(x)<<endl;
else if (s[1]=='T')	Top(x);
else if (s[1]=='B')	Bottom(x);
}
return 0;
}

``````