题目描述
Sally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。
Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过Sally的记忆力是非常好的，所以每次放书的时候至少能够那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。
当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的Sally会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。
久而久之，Sally的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(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
提示
30%的数据，n,m<=10000
100%的数据，n,m<=80000
题解：
关键是开一个*id[i]保存编号为i的书所在节点的编号,然后在newnode的时候更新他的位置
题目中
Insert就是交换id[x]和他的前驱的id的值，然后再换节点对应的编号.
Bottom就是删掉该节点，在把它的位置改成maxn+1(使得他的编号比任何一个节点都大，就达到了放在底端的效果)，maxn表示当前最大的编号，并把maxn++.Top同理
Query就是把x转到根，然后答案就是左子节点的size
Ask 就是排名为k的数
然后就开始乱搞
我犯的低级错误：
1.insert y=0时没特判
2.把第一个数放在顶端也没特判
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N=,INF=;
struct node
{
int x,size,book;
node *child[],*fa;
}a[N*];
node *pos=a,*root,*id[N];
void newnode(node *&r,int key,node *ff,int number)
{
r=pos++;
r->size=,id[number]=r;
r->x=key;r->fa=ff;r->book=number;
r->child[]=r->child[]=NULL;
}
int gi()
{
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>=''&& ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int n,m;
void updata(node *&r)
{
if(r){
r->size=(r->child[]?r->child[]->size:)+(r->child[]?r->child[]->size:)+;
return ;
}
}
void rotate(node *&r,bool t)
{
node *y=r->fa;
y->child[!t]=r->child[t];
if(r->child[t])r->child[t]->fa=y;
r->fa=y->fa;
if(y->fa)y->fa->child[y->fa->child[]==y]=r;
r->child[t]=y;
y->fa=r;
updata(y);
updata(r);
updata(r->fa);
}
void splay(node *r,node *g)
{
while(r->fa!=g)
{
if(r->fa->fa==g)rotate(r,r->fa->child[]==r);
else{
node *y=r->fa;
bool t=y->fa->child[]==y;
if(y->child[t]==r)rotate(r,!t);
else rotate(y,t);
rotate(r,t);
}
}
if(g==NULL)root=r;
}
void insert(node *&r,int key,node *fa,int number)
{
if(r==NULL){
newnode(r,key,fa,number);
splay(r,NULL);
return;
}
else insert(r->child[key>r->x],key,r,number);
}
node *pre,*nxt;
char s[];
void getpre(node *r,int key)
{
if(!r)return ;
if(r->x>=key)getpre(r->child[],key);
else pre=r,getpre(r->child[],key);
}
void getnext(node *r,int key)
{
if(!r)return ;
if(r->x<=key)getnext(r->child[],key);
else nxt=r,getnext(r->child[],key);
}
void Ask(int x)
{
splay(id[x],NULL);
printf("%d\n",root->child[]?root->child[]->size:);
return ;
}
int getrank(node *r,int rk)
{
while(r){
int d=r->child[]?r->child[]->size:;
if(rk==d+)return r->book;
if(rk<d+)r=r->child[];
else rk-=d+,r=r->child[];
}
return -;
}
node *findmax(node *r)
{
if(r->child[])return findmax(r->child[]);
else return r;
}
int maxn=,minn=;
void Delet(int x)
{
node *y;
splay(id[x],NULL);
if(root->child[]){
y=findmax(root->child[]);
splay(y,root);
y->child[]=root->child[];
y->fa=NULL;
if(root->child[])
root->child[]->fa=y;
root=y;
updata(y);
}
else{
root=root->child[];
root->fa=NULL;
}
}
void Totop(int x,bool t)
{
Delet(x);
if(!t)
insert(root,--minn,NULL,x);
else
insert(root,++maxn,NULL,x);
}
void change(int x,int y)
{
node *kl;
if(y==)getnext(root,id[x]->x),kl=nxt;
else getpre(root,id[x]->x),kl=pre;
y=kl->book;
swap(id[x],id[y]);
swap(id[x]->book,id[y]->book);
}
int main()
{
int x,y;
n=gi();m=gi();maxn=n;
for(int i=;i<=n;i++){
x=gi();
insert(root,i,NULL,x);
}
int cc=;
while(m--){
scanf("%s%d",s,&x);
if(s[]=='A')Ask(x);
else if(s[]=='Q')printf("%d\n",getrank(root,x));
else if(s[]=='I'){scanf("%d",&y);if(y)change(x,y);}
else if(s[]=='T')Totop(x,);
else if(s[]=='B')Totop(x,);
}
return ;
}