题目描述
小 T 有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 (1) 到 (n) 的正整数给每本书都编了号。
小 T 在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小 T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有 (x) 本书，那么放回去时这本书上面就只可能有 (x−1)、(x)或 (x+1) 本书。
当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小 T 会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。
久而久之，小 T 的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：
- 编号为 (x) 的书在书柜的什么位置。
- 从上到下第 (i) 本书的编号是多少。
思路
这道题的难点在于如何把编号和位置联系起来。支持一个根据编号找位置的操作。
这里令每本书的编号为权值，每本书的位置为排名
首先要把每个点权((x))初始对应的编号（放在树里的，就是(tot)）记录下来。
(pos[x]=tot)
并维护树上结点的父亲节点（马上解释为什么）
每查询一个权值，就先把它的初始编号取出来，根据初始编号一直往上跳，
初始排名为自己的左子树大小+1
两种情况：
它是父亲的右儿子：它的排名要加上它父亲的左儿子的(size) ，然后往上跳
它是父亲的左儿子：排名不变，往上跳
跳到根节点，返回排名（此权值的位置）
能够由编号得到位置，问题也就解决了大半(≧▽≦)/啦啦啦
一点细节
插入操作（Insert）：
找到前驱/后继交换位置时要精准。
以(t==-1)为例：
NEW1，NEW2表示合并顺序
ASK
得到位置后记得减(1)
Query
这里直接给的位置，不用把(pos[s])取出来了！！！
Code
#include<bits/stdc++.h>
#define N (160010)
using namespace std;
struct xbk{int l,r,rd,v,sz,fa;}t[N];
int n,m,tot,rt,pos[N];
string opt;
inline int read(){
int w=0;
bool f=0;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return f?-w:w;
}
inline void update(int p){
t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1;
if(t[p].l) t[t[p].l].fa=p;
if(t[p].r) t[t[p].r].fa=p;
return;
}
inline int New(int val){
t[++tot].sz=1;
t[tot].rd=rand();
t[tot].v=val;
t[tot].l=t[tot].r=t[tot].fa=0;
return tot;
}
inline void split(int p,int k,int &a,int &b){
if(!p) a=b=0;
else{
if(t[t[p].l].sz<k){
a=p;
split(t[p].r,k-t[t[p].l].sz-1,t[p].r,b);
}
else{
b=p;
split(t[p].l,k,a,t[p].l);
}
update(p);
}
return;
}
inline int merge(int a,int b){
if(!a||!b) return a+b;
if(t[a].rd<t[b].rd){
t[b].l=merge(a,t[b].l);
update(b);
return b;
}
else{
t[a].r=merge(t[a].r,b);
update(a);
return a;
}
return 0;
}
inline int getpos(int p){
int res=t[t[p].l].sz+1;
while(t[p].fa){
if(p==t[t[p].fa].r) res+=t[t[t[p].fa].l].sz+1;
p=t[p].fa;
}
return res;
}
int main(){
t[0].sz=t[0].fa=t[0].v=0;
n=read(),m=read();
for(int i=1;i<=n;i++){
int x=read();
rt=merge(rt,pos[x]=New(x));
}
for(int i=1;i<=m;i++){
cin>>opt;
int a,b,c,d,s,x,f;
if(opt[0]=='T'){
s=read();
x=getpos(pos[s]);
split(rt,x-1,a,b);
split(b,1,b,c);
rt=merge(merge(b,a),c);
}
if(opt[0]=='B'){
s=read();
x=getpos(pos[s]);
split(rt,x-1,a,b);
split(b,1,b,c);
rt=merge(merge(a,c),b);
}
if(opt[0]=='I'){
s=read(),f=read();
if(!f) continue;
x=getpos(pos[s]);
split(rt,x-1,a,b);
split(b,1,b,c);
if(f==1){
split(c,1,c,d);
rt=merge(merge(merge(a,c),b),d);
}
if(f==-1){
split(a,x-2,a,d);
rt=merge(merge(merge(a,b),d),c);
}
}
if(opt[0]=='A'){
s=read();
x=getpos(pos[s])-1;
printf("%d
",x);
}
if(opt[0]=='Q'){
x=read();
split(rt,x-1,a,b);
split(b,1,b,c);
printf("%d
",t[b].v);
rt=merge(merge(a,b),c);
}
}
return 0;
}