单点插入删除以及求前缀
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=,inf=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,root;
int c[M][],size[M],fa[M],v[M],pos[M];
void up(int k){size[k]=size[c[k][]]+size[c[k][]]+;}
void rotate(int x,int& k){
int y=fa[x],z=fa[y],l=,r=;
if(c[y][]==x) l=,r=;
if(y==k) k=x;
else{if(c[z][]==y) c[z][]=x; else c[z][]=x;}
fa[y]=x; fa[x]=z; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
up(y); up(x);
}
void splay(int x,int& k){
while(x!=k){
int y=fa[x],z=fa[y];
if(y!=k){
if(c[z][]==y^c[y][]==x) rotate(y,k);
else rotate(x,k);
}
rotate(x,k);
}
}
int find(int x,int rank){
int l=c[x][],r=c[x][];
if(size[l]+==rank) return x;
else if(size[l]>=rank) return find(l,rank);
else return find(r,rank-size[l]-);
}
int build(int l,int r){
if(l>r) return ;
int m=(l+r)>>;
c[m][]=build(l,m-);
c[m][]=build(m+,r);
for(int i=;i<;i++) if(c[m][i]) fa[c[m][i]]=m;
up(m); return m;
}
void del(int k){
int x,y,z;
x=find(root,k-); y=find(root,k+);
splay(x,root); splay(y,c[x][]);
z=c[y][]; c[y][]=; size[z]=fa[z]=;
up(y); up(x);
}
void move(int k,int w){
int x,y,z=pos[k],rank;
splay(z,root); rank=size[c[z][]]+;
del(rank);
if(w==-inf) x=find(root,),y=find(root,);
else if(w==inf) x=find(root,n),y=find(root,n+);
else x=find(root,rank+w-),y=find(root,rank+w);
splay(x,root); splay(y,c[x][]);
size[z]=; fa[z]=y; c[y][]=z;
up(y); up(x);
}
int main()
{
int k,T;
n=read(); m=read();
for(int i=;i<=n+;i++) v[i]=read(),pos[v[i]]=i;
root=build(,n+);
char ch[];
while(m--){
scanf("%s",ch); k=read();
if(ch[]=='T') move(k,-inf);
if(ch[]=='B') move(k,inf);
if(ch[]=='I') T=read(),move(k,T);
if(ch[]=='A') splay(pos[k],root),printf("%d\n",size[c[pos[k]][]]-);
if(ch[]=='Q') T=find(root,k+),printf("%d\n",v[T]);
}
return ;
}