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

Solution

这个题还是很裸的，只不过我犯了一个非常sb的错误然后调了好久emm……

操作原理在函数中

Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #define N (100000+100)  6 using namespace std;  7 int Size[N],Key[N];//key存编号  8 int Father[N],Son[N][2];  9 int n,m,Root,a[N],x,t; 10 int point[N];//存编号i对应的是splay的哪个点 11 char s[N]; 12  13 int Get(int x){
    return Son[Father[x]][1]==x;} 14 void Update(int x){Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1;} 15 void Clear(int x){Father[x]=Son[x][0]=Son[x][1]=Size[x]=0;} 16 int Pre(){
    int now=Son[Root][0];    while (Son[now][1]) now=Son[now][1];return now;} 17 int Next(){    int now=Son[Root][1];while (Son[now][0]) now=Son[now][0];return now;} 18  19 void Build(int l,int r,int fa) 20 { 21     if (l>r) return; 22     if (l==r) 23     { 24         Size[l]=1; 25         Key[l]=a[l]; 26         Father[l]=fa; 27         Son[fa][l>fa]=l; 28         return; 29     } 30     int mid=(l+r)/2; 31     Build(l,mid-1,mid); 32     Build(mid+1,r,mid); 33     Father[mid]=fa; 34     Son[fa][mid>fa]=mid; 35     Key[mid]=a[mid]; 36     Update(mid); 37 } 38  39 void Rotate(int x) 40 { 41     int wh=Get(x); 42     int fa=Father[x],fafa=Father[fa]; 43     Son[fa][wh]=Son[x][wh^1]; 44     Father[fa]=x; 45     if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 46     Son[x][wh^1]=fa; 47     Father[x]=fafa; 48     if (fafa) Son[fafa][Son[fafa][1]==fa]=x; 49     Update(fa); 50     Update(x); 51 } 52  53 void Splay(int x) 54 { 55     for (int fa; fa=Father[x]; Rotate(x)) 56         if (Father[fa]) 57             Rotate(Get(fa)==Get(x)?fa:x); 58     Root=x; 59 } 60  61 int Findx(int x) 62 { 63     int now=Root; 64     while (1) 65         if (x<=Size[Son[now][0]]) 66             now=Son[now][0]; 67         else 68         { 69             x-=Size[Son[now][0]]; 70             if (x==1) 71             { 72                 Splay(now); 73                 return Key[now]; 74             } 75             x--; 76             now=Son[now][1]; 77         } 78 } 79  80 void Delete(int x) 81 { 82     Findx(x); 83     if (!Son[Root][0] && !Son[Root][1]) 84     { 85         Clear(Root); 86         Root=0; 87         return; 88     } 89     if (!Son[Root][1]) 90     { 91         Root=Son[Root][0]; 92         Clear(Father[Root]); 93         Father[Root]=0; 94         return; 95     } 96     if (!Son[Root][0]) 97     { 98         Root=Son[Root][1]; 99         Clear(Father[Root]);100         Father[Root]=0;101         return;102     }103     Splay(x);104     int pre=Pre(),old=x;105     Splay(pre);106     Son[Root][1]=Son[old][1];107     Father[Son[old][1]]=Root;108     Clear(old);109     Update(Root);110 }111 112 void Top(int x)//就是将一个点删除掉然后放到哨兵节点1的右儿子上。若右儿子有点就把原来的右儿子当做插入节点的右儿子113 {114     Delete(x);115     int now=Root;116     while (Son[now][0]) now=Son[now][0];117     int old=Son[now][1];118     Father[x]=now;119     Son[now][1]=x;120     Father[old]=x;121     Son[x][1]=old;122     Update(x);123     Splay(x);124 }125 126 void Bottom(int x)//同上127 {128     Delete(x);129     int now=Root;130     while (Son[now][1]) now=Son[now][1];131     int old=Son[now][0];132     Father[x]=now;133     Son[now][0]=x;134     Father[old]=x;135     Son[x][0]=old;136     Update(now);137     Splay(x);138 }139 140 void Ins(int x,int t)//-1(+1同理)：先把x删掉，再把x前驱splay到根，再把x插到根的前驱位置的叶子141 {142     int y,z;143     if (t==-1)144     {145         Splay(x);146         y=Pre();147         Delete(x);148         Splay(y);149         z=Pre();150         Father[x]=z;151         Son[z][1]=x;152         Size[x]=1;153         Update(z);154         Splay(x);155     }156     if (t==1)157     {158         Splay(x);159         y=Next();160         Delete(x);161         Splay(y);162         z=Next();163         Father[x]=z;164         Son[z][0]=x;165         Size[x]=1;166         Update(z);167         Splay(x);168     }169 170 }171 172 int Ask(int x)//emmm……173 {174     Splay(x);175     return Size[Son[x][0]]-1;176 }177 178 int main()179 {180     scanf("%d%d",&n,&m);181     for (int i=1; i<=n; ++i)182     {183         scanf("%d",&a[i+1]);184         point[a[i+1]]=i+1;185     }186     Build(1,n+2,0);187     Root=(n+3)/2;188     for (int i=1; i<=m; ++i)189     {190         scanf("%s%d",&s,&x);191         if (s[0]=='T') Top(point[x]);192         if (s[0]=='B') Bottom(point[x]);193         if (s[0]=='I') scanf("%d",&t),Ins(point[x],t);194         if (s[0]=='A') printf("%d\n",Ask(point[x]));195         if (s[0]=='Q') printf("%d\n",Findx(x+1));196     }197 }