```cpp
#include<bits/stdc++.h>
#define maxn 1000001
#define L(node) (tree[node].ch[0])
#define R(node) (tree[node].ch[1])
#define F(node) (tree[node].fa)
using namespace std;
struct kkk{
int ch[2],val,size,fa;
kkk(){ch[0]=ch[1]=val=size=fa=0;}
}tree[maxn];
int n,m,x,y,top,cnt,root,answ;
int pos[maxn];
char MODE[11];
void pushup(int node){
tree[node].size=tree[L(node)].size+tree[R(node)].size+1;
pos[tree[L(node)].val]=L(node);
pos[tree[R(node)].val]=R(node);
}
void rotate(int node){
int fa=F(node);
int gfa=F(fa);
int z=tree[fa].ch[1]==node;
tree[gfa].ch[tree[gfa].ch[1]==fa]=node; tree[node].fa=gfa;
tree[fa].ch[z]=tree[node].ch[z^1]; tree[tree[node].ch[z^1]].fa=fa;
tree[node].ch[z^1]=fa; tree[fa].fa=node;
pushup(fa); pushup(node);
}
void Splay(int node,int goal){
while(tree[node].fa!=goal){
int fa=F(node);
int gfa=F(fa);
if(gfa!=goal)
((tree[gfa].ch[1]==fa)==(tree[fa].ch[1]==node))?rotate(fa):rotate(node);
rotate(node);
}
pos[tree[node].val]=node;
if(!goal)root=node;
}
int kth(int x){
int node=root;
while(1){
if(tree[L(node)].size>=x)node=L(node);
else{ x-=tree[L(node)].size;
if(x==1) return tree[node].val;
x--;node=R(node);
}
}
}
void Top_Bottom(int x,int mode){
Splay(pos[x],0);
if(!tree[root].ch[mode])return ;
if(!tree[root].ch[!mode]) tree[root].ch[!mode]=tree[root].ch[mode],tree[root].ch[mode]=0;
else{
int node=tree[root].ch[!mode];while(tree[node].ch[mode])node=tree[node].ch[mode];
tree[tree[root].ch[mode]].fa=node; tree[node].ch[mode]=tree[root].ch[mode];
tree[root].ch[mode]=0;
Splay(tree[node].ch[mode],0);
}
}
void Ins(int x,int mode){
Splay(pos[x],0);
if(!mode)return ;
if(mode==1){
int node=R(root);
while(L(node))node=L(node);
swap(pos[x],pos[tree[node].val]);
swap(tree[pos[x]].val,tree[node].val);
}else{
int node=L(root);
while(R(node))node=R(node);
swap(pos[x],pos[tree[node].val]);
swap(tree[pos[x]].val,tree[node].val);
}
}
void ask(int x){
Splay(pos[x],0);answ++;
printf("%d\n",tree[L(root)].size);
}
void query(int x){answ++;
printf("%d\n",kth(x));
}
void New(int node,int val,int fa){
tree[node].val=val;tree[node].fa=fa;
tree[node].ch[0]=tree[node].ch[1]=0;
tree[node].size=1;pos[val]=node;
}
void insert(int x){
int node=root;
while(R(root))node=R(root);
cnt++;
tree[cnt].fa=node;
tree[node].ch[1]=cnt;
tree[cnt].val=x;pos[x]=cnt;
tree[cnt].size=1;
tree[cnt].ch[0]=tree[cnt].ch[1]=0;
Splay(cnt,0);
}
void print(int node){
if(L(node))print(L(node));
printf("%d\n",tree[node].val);
if(R(node))print(R(node));
}
int main(){
scanf("%d%d",&n,&m);cnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&x);/*cnt++;
New(cnt,x,cnt-1);
tree[cnt-1].ch[1]=cnt;
Splay(cnt,0);*/
insert(x);
}
//print(root);
for(int i=1;i<=m;i++){
scanf("%s",MODE);
scanf("%d",&x);
if(MODE[0]=='T')Top_Bottom(x,0);
if(MODE[0]=='B')Top_Bottom(x,1);
if(MODE[0]=='I')scanf("%d",&y),Ins(x,y);
if(MODE[0]=='A')ask(x);
if(MODE[0]=='Q')query(x);
}
return 0;
}
```
by hyfhaha @ 2019-04-25 22:24:56
你都看题解了，为啥不对着题解改完呢？（雾
by Luvwgyx @ 2019-04-26 08:18:33
@[Luvwgyx](/space/show?uid=43012) 就是找不到错啊QAQ
by hyfhaha @ 2019-04-26 19:04:45