Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的 书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能 有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。 久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作， 以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

Input

第 一行有两个数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本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

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

Sample Output

2

9

9

7

5

3

HINT

数据范围

100%的数据，n,m < = 80000

Source

 

 

MDZZ

明天菊儿子要考平衡树。。。。

爸爸要跪烂了。。。

估计停课期间会从头爆零爆到尾。。。

我的splay水平还是太烂了。。。对splay的理解和熟练程度都有待加强。。。。

 

我都不知道我这菜鸡splay水平是怎么把LCT学会的。。。

这个题的操作涉及删除和插入以及询问排名和某排名上的数值。。。。

好吧。。。一听就是裸splay。。。

今天get了一个黑科技。。。在读入的首尾各加一个元素可以避免删除时的边界特判。。。（Orz贼有道理）；

再复习几个操作吧，纯粹为了练板子：

find:查询排名为x的点。。。

query查询数x的排名。。。

del删除x。。。

change 删除再插入。。。

1 // MADE BY QT666  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 #include
             
               10 #include
              
                11 #include
               
                 12 #define lson num<<1 13 #define rson num<<1|1 14 using namespace std; 15 typedef long long ll; 16 const int N=100050; 17 const int inf=2147483647; 18 int gi() 19 { 20 int x=0,flag=1; 21 char ch=getchar(); 22 while(ch<'0'||ch>'9'){ if(ch=='-') flag=-1;ch=getchar();} 23 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); 24 return x*flag; 25 } 26 int c[N][2],fa[N],id[N],n,m,rt,sz; 27 int size[N],a[N],v[N]; 28 char ch[N]; 29 void update(int x) 30 { 31 int l=c[x][0],r=c[x][1]; 32 size[x]=size[l]+size[r]+1; 33 } 34 void rotate(int x,int &k) 35 { 36 int y=fa[x],z=fa[y],l,r; 37 if(c[y][0]==x) l=0;else l=1;r=l^1; 38 if(y==k) k=x; 39 else 40 { 41 if(c[z][0]==y) c[z][0]=x; 42 else c[z][1]=x; 43 } 44 fa[y]=x;fa[x]=z;fa[c[x][r]]=y; 45 c[y][l]=c[x][r];c[x][r]=y; 46 update(y);update(x); 47 } 48 void splay(int x,int &k) 49 { 50 while(x!=k) 51 { 52 int y=fa[x],z=fa[y]; 53 if(y!=k) 54 { 55 if((c[y][0]==x)^(c[z][0]==y)) rotate(x,k); 56 else rotate(y,k); 57 } 58 rotate(x,k); 59 } 60 } 61 int find(int x,int rk) 62 { 63 int l=c[x][0],r=c[x][1]; 64 if(size[l]+1==rk) return x; 65 else if(size[l]>=rk) return find(l,rk); 66 else return find(r,rk-size[l]-1); 67 } 68 void del(int k) 69 { 70 int x,y,z; 71 x=find(rt,k-1),y=find(rt,k+1); 72 splay(x,rt);splay(y,c[x][1]); 73 z=c[y][0],c[y][0]=0;fa[z]=size[z]=0; 74 } 75 void build(int l,int r,int f) 76 { 77 if(l>r)return; 78 int mid=(l+r)>>1; 79 if(l==r) v[l]=a[l],size[l]=1; 80 else build(l,mid-1,mid),build(mid+1,r,mid); 81 v[mid]=a[mid];fa[mid]=f;update(mid); 82 if(mid
                
                 >1;107 int x,y;108 for(int i=1;i<=m;i++)109 {110 scanf("%s",ch+1); x=gi();111 if(ch[1]=='T') change(x,-inf);112 if(ch[1]=='B') change(x,inf);113 if(ch[1]=='I') y=gi(),change(x,y);114 if(ch[1]=='A') printf("%d\n",query(x));115 if(ch[1]=='Q') printf("%d\n",v[find(rt,x+1)]);116 }117 return 0;118 }