题目描述
小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。
小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。
当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。
久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。
输入输出格式
输入格式：第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式：
1． Top S——表示把编号为S的书放在最上面。
2． Bottom S——表示把编号为S的书放在最下面。
3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书；
4． Ask S——询问编号为S的书的上面目前有多少本书。
5． Query S——询问从上面数起的第S本书的编号。
输出格式：对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。
输入输出样例
10 10 1 3 2 7 5 8 10 4 9 6 Query 3 Top 5 Ask 6 Bottom 3 Ask 3 Top 6 Insert 4 -1 Query 5 Query 2 Ask 2
2 9 9 7 5 3
说明
100%的数据，n,m <= 80000
代码
虚拟一个节点高度，把高度作为数列进行维护
T：删除编号为S的书，插入一个虚拟高度为当前最小且编号为S的书
B：同T，插入虚拟高度为当前最大
I：交换前驱或后继的信息
A：查询rank
Q：查询kth
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn=1000000+100; int ch[maxn][2],fa[maxn],size[maxn],cnt[maxn],id[maxn],val[maxn],pos[maxn]; char op[10]; //表示节点编号，val表示节点虚拟高度,pos表id所在位置 int root,ncnt; int mi,mx; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } void output(int u=root) { if(ch[u][0])output(ch[u][0]); if(val[u]==inf||val[u]==-inf)return; printf("%d ",id[u]); if(ch[u][1])output(ch[u][1]); } void pushup(int u) { size[u]=size[ch[u][0]]+size[ch[u][1]]+cnt[u]; } int chk(int u) { return ch[fa[u]][1]==u; } void rotate(int u) { int f=fa[u],ff=fa[f],k=chk(u),s=ch[u][k^1]; ch[f][k]=s,fa[s]=f; ch[ff][chk(f)]=u,fa[u]=ff; ch[u][k^1]=f,fa[f]=u; pushup(u),pushup(f); } void splay(int u,int goal=0) { while(fa[u]!=goal) { int f=fa[u],ff=fa[f]; if(ff!=goal) { if(chk(u)==chk(f))rotate(f); else rotate(u); } rotate(u); } if(!goal)root=u; } void insert(int x,int y) { int u=root,f=0; while(u&&val[u]!=x) f=u,u=ch[u][x>val[u]]; u=++ncnt; if(f)ch[f][x>val[f]]=u; fa[u]=f,val[u]=x,id[u]=y,pos[y]=u; size[u]=cnt[u]=1; ch[u][0]=ch[u][1]=0; splay(u); } int kth(int k) { int u=root; while(1) { if(ch[u][0]&&k<=size[ch[u][0]]) u=ch[u][0]; else if(k>size[ch[u][0]]+cnt[u]) k-=size[ch[u][0]]+cnt[u],u=ch[u][1]; else return u; } } int ask(int x) { splay(pos[x]); return size[ch[root][0]]-1; } int pre(int u) { splay(u); u=ch[root][0]; while(ch[u][1])u=ch[u][1]; return u; } int succ(int u) { splay(u); u=ch[root][1]; while(ch[u][0])u=ch[u][0]; return u; } void remove(int u) { int last=pre(u),next=succ(u); splay(last),splay(next,last); ch[next][0]=0; } void top(int s) { remove(pos[s]); insert(--mi,s); } void bottom(int s) { remove(pos[s]); insert(++mx,s); } void change(int u,int o) { int now=pos[u]; if(o==1) { int next=succ(now); if(!id[next])return; pos[u]=next,pos[id[next]]=now; swap(id[now],id[next]); } if(o==-1) { int last=pre(now); if(!id[last])return; pos[u]=last,pos[id[last]]=now; swap(id[now],id[last]); } } int main() { insert(inf,0),insert(-inf,0); int n=read(),m=read(); mi=0,mx=n+1; for(int i=1;i<=n;i++) insert(i,read()); for(int i=1;i<=m;i++) { cin>>op; if(op[0]=='T'){int x=read();top(x);} if(op[0]=='B'){int x=read();bottom(x);} if(op[0]=='I'){int x=read(),y=read();change(x,y);} if(op[0]=='A'){int x=read();printf("%d ",ask(x));} if(op[0]=='Q'){int x=read();printf("%d ",id[kth(x+1)]);} } return 0; }