这题想写三次了。结果前两次太困╯﹏╰没写成，大数据结构题就是烦人啊。
没什么值得注意的，就按题意一步步来吧。（写了map表示对应树上位置，担心编号大爆掉，不加好像也没啥关系）
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> using namespace std; struct node { int x,c,f,son[2]; }tr[110000];int len,root; void update(int x)//use for c { int lc=tr[x].son[0],rc=tr[x].son[1]; tr[x].c=tr[lc].c+tr[rc].c+1; } void rotate(int x,int w) { int f=tr[x].f,ff=tr[f].f; int R,r; R=f,r=tr[x].son[w]; tr[R].son[1-w]=r; if(r!=0)tr[r].f=R; R=ff,r=x; if(tr[R].son[0]==f)tr[R].son[0]=r; else if(tr[R].son[1]==f)tr[R].son[1]=r; tr[r].f=R; R=x;r=f; tr[R].son[w]=r; tr[r].f=R; update(f); update(x); } void splay(int x,int rt) { while(tr[x].f!=rt) { int f=tr[x].f,ff=tr[f].f; if(ff==rt) { if(tr[f].son[0]==x)rotate(x,1); else rotate(x,0); } else { if(tr[ff].son[0]==f&&tr[f].son[0]==x){rotate(f,1);rotate(x,1);} else if(tr[ff].son[1]==f&&tr[f].son[1]==x){rotate(f,0);rotate(x,0);} else if(tr[ff].son[0]==f&&tr[f].son[1]==x){rotate(x,0);rotate(x,1);} else if(tr[ff].son[1]==f&&tr[f].son[0]==x){rotate(x,1);rotate(x,0);} } } if(rt==0)root=x; } //----------splay_in------------------- void ins(int x,int f,int id)//令x作为f的后一本书，编号为id { if(f==0) { if(root==0) { root=id; tr[id].x=x; tr[id].f=0; tr[id].son[0]=0; tr[id].son[1]=0; update(id); } else //make Top { int left=root; while(tr[left].son[0]!=0)left=tr[left].son[0]; //find left splay(left,0); tr[left].son[0]=id; tr[id].x=x; tr[id].f=left; tr[id].son[0]=0; tr[id].son[1]=0; update(id); update(left); splay(id,0); } } else { splay(f,0); if(tr[f].son[1]==0)//make Bottom { int right=f; tr[right].son[1]=id; tr[id].x=x; tr[id].f=right; tr[id].son[0]=0; tr[id].son[1]=0; update(id); update(right); splay(id,0); } else //simple ins { int rc=tr[f].son[1]; tr[f].son[1]=id; tr[id].x=x; tr[id].f=f; tr[id].son[0]=0; tr[id].son[1]=rc; tr[rc].f=id; update(id); update(f); splay(id,0); } } } void del(int id) { splay(id,0); if(tr[id].son[0]==0){root=tr[id].son[1];tr[tr[id].son[1]].f=0;} else if(tr[id].son[1]==0){root=tr[id].son[0];tr[tr[id].son[0]].f=0;} else { int p=tr[id].son[0]; while(tr[p].son[1]!=0)p=tr[p].son[1]; splay(p,id); int R=p,r=tr[id].son[1]; tr[R].son[1]=r; tr[r].f=R; update(p); root=p;tr[p].f=0; } } //-------init/Top/Buttom----------- map<int,int>mp;//get某编号的树上位置 void solve(int id,int T)//insert { splay(id,0); if(T==-1) { int p=tr[id].son[0]; while(tr[p].son[1]!=0)p=tr[p].son[1]; splay(p,id); //exchange int t1=tr[id].x,t2=tr[p].x; swap(tr[id].x,tr[p].x); mp[t1]=p;mp[t2]=id; } else { int p=tr[id].son[1]; while(tr[p].son[0]!=0)p=tr[p].son[0]; splay(p,id); int t1=tr[id].x,t2=tr[p].x; swap(tr[id].x,tr[p].x); mp[t1]=p;mp[t2]=id; } } int query(int k) { int now=root; while(1) { int lc=tr[now].son[0],rc=tr[now].son[1]; if(tr[lc].c+1==k)return tr[now].x; else if(tr[lc].c>=k)now=lc; else k-=tr[lc].c+1, now=rc; } } char ss[20]; int main() {int n,m,x,last=0; scanf("%d%d",&n,&m); len=root=0; for(int i=1;i<=n;i++) { scanf("%d",&x); ins(x,last,++len); last=len; mp[x]=len; } int S,T; while(m--) { scanf("%s",ss+1); if(ss[1]=='T') { scanf("%d",&S); int id=mp[S],x=tr[id].x; del(id); ins(x,0,id); } else if(ss[1]=='B') { scanf("%d",&S); int id=mp[S],x=tr[id].x; del(id); int right=root; while(tr[right].son[1]!=0)right=tr[right].son[1]; //find right ins(x,right,id); } else if(ss[1]=='I') { scanf("%d%d",&S,&T); if(T==0)continue; solve(mp[S],T); } else if(ss[1]=='A') { scanf("%d",&S); int id=mp[S]; splay(id,0);printf("%d ",tr[tr[id].son[0]].c); } else { scanf("%d",&S); printf("%d ",query(S)); } } return 0; }