小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语句你应该输出一行，一个数，代表询问的答案。

数据范围

Day2

  1 /**  2  * bzoj  3  * Problem#1861  4  * Accepted  5  * Time:1280ms  6  * Memory:3464k  7  */  8 #include<iostream>  9 #include<fstream> 10 #include<sstream> 11 #include<cstdio> 12 #include<cstdlib> 13 #include<cstring> 14 #include<ctime> 15 #include<cctype> 16 #include<cmath> 17 #include<algorithm> 18 #include<stack> 19 #include<queue> 20 #include<set> 21 #include<map> 22 #include<vector> 23 using namespace std; 24 typedef bool boolean; 25 #define smin(a, b)    (a) = min((a), (b)) 26 #define smax(a, b)    (a) = max((a), (b)) 27 template<typename T> 28 inline void readInteger(T& u){ 29     char x; 30     int aFlag = 1; 31     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 32     if(x == -1)    return; 33     if(x == ‘-‘){ 34         x = getchar(); 35         aFlag = -1; 36     } 37     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - ‘0‘); 38     ungetc(x, stdin); 39     u *= aFlag; 40 } 41  42 template<typename T> 43 class SplayNode{ 44     public: 45         T data; 46         int s; 47         SplayNode* next[2]; 48         SplayNode* father; 49         SplayNode(T data, SplayNode* father):data(data), father(father), s(1){ 50             memset(next, 0, sizeof(next)); 51         } 52         inline void maintain(){ 53             this->s = 1; 54             for(int i = 0; i < 2; i++) 55                 if(next[i] != NULL) 56                     s += next[i]->s; 57         } 58         int which(SplayNode* p){ 59             return (next[0] == p) ? (0) : (1); 60         } 61 }; 62  63 template<typename T> 64 class Splay{ 65     protected: 66         inline static void rotate(SplayNode<T>*& node, int d){ 67             SplayNode<T> *father = node->father; 68             SplayNode<T> *newRoot = node->next[d ^ 1]; 69             node->next[d ^ 1] = newRoot->next[d]; 70             node->father = newRoot; 71             newRoot->next[d] = node; 72             newRoot->father = father; 73             if(node->next[d ^ 1] != NULL)    node->next[d ^ 1]->father = node; 74             if(father != NULL)    father->next[father->which(node)] = newRoot; 75             node->maintain(); 76             node->father->maintain(); 77         } 78          79         static SplayNode<T>* findKth(SplayNode<T>*& node, int k){ 80             int ls = (node->next[0] != NULL) ? (node->next[0]->s) : (0); 81             if(k == ls + 1)    return node; 82             if(k <= ls)    return findKth(node->next[0], k); 83             return findKth(node->next[1], k - ls - 1); 84         }         85          86     public: 87         SplayNode<T>* root; 88          89         Splay():root(NULL){    } 90          91         inline void splay(SplayNode<T>*& node, SplayNode<T>* father){ 92             while(node->father != father){ 93                 SplayNode<T>* f = node->father; 94                 int fd = f->which(node); 95                 SplayNode<T>* ff = f->father; 96                 if(ff == father){ 97                     rotate(f, fd ^ 1); 98                     break; 99                 }100                 int ffd = ff->which(f);101                 if(fd == ffd){102                     rotate(ff, ffd ^ 1);103                     rotate(f, fd ^ 1);104                 }else{105                     rotate(f, fd ^ 1);106                     rotate(ff, ffd ^ 1);107                 }108             }109             if(father == NULL)110                 root = node;111         }112         113         inline SplayNode<T>* findKth(int k, SplayNode<T>* father){114             if(root == NULL || k < 1 || k > root->s)    return NULL;115             SplayNode<T>* res = findKth(root, k);116             splay(res, father);117             return res;118         }        119         120         inline void insert(T data, int index){121             if(root == NULL){122                 root = new SplayNode<T>(data, NULL);123                 return;124             }125             SplayNode<T>* added;126             if(index <= 1){127                 findKth(1, NULL);128                 added = root->next[0] = new SplayNode<T>(data, root);129             }else if(index >= root->s + 1){130                 findKth(root->s, NULL);131                 added = root->next[1] = new SplayNode<T>(data, root);132             }else if(index == root->s){133                 findKth(index, NULL);134                 findKth(index - 1, root);135                 added = new SplayNode<T>(data, root);136                 added->next[0] = root->next[0];137                 root->next[0]->father = added;138                 root->next[0] = added;139             }else{140                 findKth(index - 1, NULL);141                 findKth(index + 1, root);142                 SplayNode<T>* node = root->next[1]->next[0];143                 added = node->next[0] = new SplayNode<T>(data, node);144             }145             splay(added, NULL);146         }147         148         inline void remove(SplayNode<T>* node){149             splay(node, NULL);150             SplayNode<T>* maxi = node->next[0];151             if(maxi == NULL){152                 root = node->next[1];153                 if(node->next[1] != NULL)    node->next[1]->father = NULL;154                 delete node;155                 return;156             }157             while(maxi->next[1] != NULL) maxi = maxi->next[1];158             splay(maxi, node);159             maxi->next[1] = node->next[1];160             if(node->next[1] != NULL)    node->next[1]->father = maxi;161             maxi->father = NULL;162             delete node;163             root = maxi;164             maxi->maintain();165         }166         167 };168 169 int n, m;170 Splay<int> s;171 SplayNode<int>** books;172 173 inline void init(){174     readInteger(n);175     readInteger(m);176     books = new SplayNode<int>*[(const int)(n + 1)];177     for(int i = 1, a; i <= n; i++){178         readInteger(a);179         s.insert(a, i);180         books[a] = s.root;181     }182 }183 184 inline void solve(){185     char cmd[10];186     int a, b;187     while(m--){188         scanf("%s", cmd);189         readInteger(a);190         if(cmd[0] == ‘T‘){191             s.remove(books[a]);192             s.insert(a, 1);193             books[a] = s.root;194         }else if(cmd[0] == ‘B‘){195             s.remove(books[a]);196             s.insert(a, n);197             books[a] = s.root;198         }else if(cmd[0] == ‘I‘){199             readInteger(b);200             if(b == 0)    continue;201             s.splay(books[a], NULL);202             int r = (s.root->next[0] == NULL) ? (0) : (s.root->next[0]->s);203             s.remove(books[a]);204             s.insert(a, r + 1 + b);205             books[a] = s.root;206         }else if(cmd[0] == ‘A‘){207             s.splay(books[a], NULL);208             int r = (s.root->next[0] == NULL) ? (0) : (s.root->next[0]->s);209             printf("%d\n", r);210         }else if(cmd[0] == ‘Q‘){211             SplayNode<int> *node = s.findKth(a, NULL);212             printf("%d\n", node->data);213         }214     }215 }216 217 int main(){218     init();219     solve();220     return 0;221 }