通过这题我加深了对Splay的理解，原来Splay的子树也是可以接来接去接到别的点上的，而不是只能旋转qwq
具体接的办法就是swap大法。
对于Top操作我们把当前节点Splay到根，然后把它的左子树接到后继上。
Bottom同理
对于Insert，暴力swap当前节点和它的前驱或者后继。
Ask操作就把节点Splay到根，然后输出它的左子树有多少节点。
Query直接查就行。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#define maxn 1000010
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int pos[maxn];
int CNT=;
struct Splay{
struct Node{
int key,val,fa,e[],size;
}tree[maxn];
int tag[maxn];
int point,tot,root;
Splay(){point=tot=root=;memset(tag,,sizeof(tag)); }
inline void update(int x){ tree[x].size=tree[tree[x].e[]].size+tree[tree[x].e[]].size+; }
inline void connect(int x,int fa,int how){ tree[x].fa=fa; tree[fa].e[how]=x; }
inline int iden(int x){ return x==tree[tree[x].fa].e[]; }
inline void rotate(int x){
int y=tree[x].fa;int r=tree[y].fa;
if(y==root) root=x;
int sony=iden(x);int sonr=iden(y);
int b=tree[x].e[sony^];
connect(b,y,sony);
connect(y,x,sony^);
connect(x,r,sonr);
update(y); update(x);
}
void splay(int pos,int to){
to=tree[to].fa;
while(tree[pos].fa!=to){
if(tree[tree[pos].fa].fa==to) rotate(pos);
else
if(iden(pos)==iden(tree[pos].fa)){
rotate(tree[pos].fa);
rotate(pos);
}
else{ rotate(pos); rotate(pos); }
}
}
int create(int key,int val,int fa){
tree[++tot].val=val; tree[tot].fa=fa;
tree[tot].size=; tree[tot].key=key;
return tot;
}
int build(int key,int val){
if(root==){ root=create(key,val,); return root; }
int now=root;
while(){
tree[now].size++;
int nxt=tree[now].key>key?:;
if(tree[now].e[nxt]==){
connect(create(key,val,now),now,nxt);
return tot;
}
now=tree[now].e[nxt];
}
}
void insert(int key,int val){
int p=build(key,val);
pos[val]=p;
if(++CNT=){
CNT=;
splay(p,root);
}
}
int find(int rnk){
int now=root;
while(now){
if(tree[tree[now].e[]].size+==rnk) return now;
else if(tree[tree[now].e[]].size>=rnk) now=tree[now].e[];
else{
rnk-=tree[tree[now].e[]].size+;
now=tree[now].e[];
}
}
}
void rotop(int val){
val=pos[val];
splay(val,root);
int le=tree[val].e[];
if(le==) return;
if(tree[val].e[]==){
connect(le,val,);
tree[val].e[]=;
update(val);
}
else{
int deal=find(tree[tree[val].e[]].size+);
connect(tree[val].e[],deal,); tree[val].e[]=;
int now=deal;
while(now){
update(now);
now=tree[now].fa;
}
splay(deal,root);
}
}
void roend(int val){
val=pos[val];
splay(val,root);
int ri=tree[val].e[];
if(ri==) return;
if(tree[val].e[]==){
connect(ri,val,);
tree[val].e[]=;
update(val);
}
else{
int deal=find(tree[tree[val].e[]].size);
connect(tree[val].e[],deal,); tree[val].e[]=;
int now=deal;
while(now){
update(now);
now=tree[now].fa;
}
splay(deal,root);
}
}
void rofro(int val){
val=pos[val];
splay(val,root);
int deal=find(tree[tree[val].e[]].size);
std::swap(pos[tree[val].val],pos[tree[deal].val]);
std::swap(tree[val].val,tree[deal].val);
}
void rosub(int val){
val=pos[val];
splay(val,root);
int deal=find(tree[tree[val].e[]].size+);
std::swap(pos[tree[val].val],pos[tree[deal].val]);
std::swap(tree[val].val,tree[deal].val);
}
int rank(int key){
int now=root;
while(now){
if(tree[tree[now].e[]].size+==key) return tree[now].val;
if(tree[tree[now].e[]].size>=key) now=tree[now].e[];
else{
key-=tree[tree[now].e[]].size+;
now=tree[now].e[];
}
}
return ;
}
int arank(int val){
val=pos[val];
splay(val,root);
return tree[tree[val].e[]].size;
}
}s; int main(){
int n=read(),m=read();
for(int i=;i<=n;++i){
int x=read();
s.insert(i,x);
}
for(int i=;i<=m;++i){
char c[];int x;
scanf("%s%d",c,&x);
switch(c[]){
case 'T':{
s.rotop(x);
break;
}
case 'B':{
s.roend(x);
break;
}
case 'I':{
int y=read();
if(y==-) s.rofro(x);
if(y==) s.rosub(x);
break;
}
case 'A':{
printf("%d\n",s.arank(x));
break;
}
case 'Q':{
printf("%d\n",s.rank(x));
break;
}
}
}
return ;
}