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
题解
其实除了$Splay$，则道题还可以用$Treap$做。
以$key$为关键词，表示其在书架中的位置，若插在两本书中间，直接取$mid$就可以。
$double$有误差，建议一开始就把书架位置的公差调大。
1 #include<cmath> 2 #include<ctime> 3 #include<queue> 4 #include<stack> 5 #include<cstdio> 6 #include<string> 7 #include<cstdlib> 8 #include<cstring> 9 #include<iostream> 10 #include<algorithm> 11 using namespace std; 12 const int N=160000; 13 const int X=0.00000001; 14 15 struct node 16 { 17 double key; 18 int lev,num,low; 19 node *child[2]; 20 } T[N+5],*root,*pos; 21 double key[N+5],miner,maxer; 22 int n,m,x,y; 23 char c; 24 25 void NewNode(node* &r,double key,int num); 26 void Insert(node* &r,double key,int num); 27 void Delete(node* &r,double key); 28 int Query(node* r,int rank,int cnt); 29 int Ask(node* r,double key); 30 void Rotate(node* &r,bool t); 31 int Count(node* r); 32 double my_abs(double x) {return x<0 ? -x:x;} 33 int Read(); 34 35 int main() 36 { 37 srand(time(0)); 38 root=NULL; 39 pos=T; 40 n=Read(); 41 m=Read(); 42 miner=1; 43 maxer=n; 44 for (int i=1;i<=n;i++) 45 { 46 x=Read(); 47 key[x]=i; 48 Insert(root,key[x],x); 49 } 50 while(m--) 51 { 52 c=0; 53 while(c<'A'||c>'Z') c=getchar(); 54 if (c=='T') 55 { 56 x=Read(); 57 Delete(root,key[x]); 58 key[x]=--miner; 59 Insert(root,key[x],x); 60 } 61 else if (c=='B') 62 { 63 x=Read(); 64 Delete(root,key[x]); 65 key[x]=++maxer; 66 Insert(root,key[x],x); 67 } 68 else if (c=='I') 69 { 70 x=Read(); 71 y=Read(); 72 if (y==0) continue; 73 int a=Ask(root,key[x]); 74 if (a==n-1&&y==1) 75 { 76 Delete(root,key[x]); 77 key[x]=++maxer; 78 Insert(root,key[x],x); 79 continue; 80 } 81 if (a==2&&y==-1) 82 { 83 Delete(root,key[x]); 84 key[x]=--miner; 85 Insert(root,key[x],x); 86 continue; 87 } 88 Delete(root,key[x]); 89 if (y==1) key[x]=(key[Query(root,a,0)]+key[Query(root,a+y,0)])/2.0; 90 else key[x]=(key[Query(root,a+y,0)]+key[Query(root,a+y*2,0)])/2.0; 91 Insert(root,key[x],x); 92 } 93 else if (c=='A') 94 { 95 x=Read(); 96 printf("%d ",Ask(root,key[x])-1); 97 } 98 else if (c=='Q') 99 { 100 x=Read(); 101 printf("%d ",Query(root,x,0)); 102 } 103 else break; 104 } 105 return 0; 106 } 107 108 int Read() 109 { 110 int sum=0; 111 bool ok=0; 112 c=0; 113 while ((c<'0'||c>'9')&&c!='-') c=getchar(); 114 if (c=='-') 115 { 116 ok=1; 117 c=getchar(); 118 } 119 while (c>='0'&&c<='9') 120 { 121 sum=sum*10+c-'0'; 122 c=getchar(); 123 } 124 return ok ? -sum:sum; 125 } 126 void NewNode(node* &r,double key,int num) 127 { 128 r=pos++; 129 r->key=key; 130 r->num=num; 131 r->low=1; 132 r->lev=rand(); 133 } 134 void Insert(node* &r,double key,int num) 135 { 136 if (!r) 137 { 138 NewNode(r,key,num); 139 return; 140 } 141 bool t=key>r->key; 142 if (!t) r->low++; 143 Insert(r->child[t],key,num); 144 if (r->child[t]->lev<r->lev) 145 { 146 Rotate(r,!t); 147 r->low=1+Count(r->child[0]); 148 } 149 } 150 void Delete(node* &r,double key) 151 { 152 if (my_abs(r->key-key)<=X) 153 { 154 if (r->child[0]&&r->child[1]) 155 { 156 bool t=r->child[0]->lev<r->child[1]->lev; 157 Rotate(r,t); 158 r->low=1+Count(r->child[0]); 159 if (!t) r->low--; 160 Delete(r->child[t],key); 161 } 162 else 163 { 164 if (r->child[0]) r=r->child[0]; 165 else r=r->child[1]; 166 } 167 } 168 else 169 { 170 bool t=key>r->key; 171 if (!t) r->low--; 172 Delete(r->child[t],key); 173 } 174 } 175 void Rotate(node* &r,bool t) 176 { 177 node *y=r->child[!t],*R=r; 178 r->child[!t]=y->child[t]; 179 y->child[t]=r; 180 r=y; 181 R->low=1+Count(R->child[0]); 182 } 183 int Query(node* r,int rank,int cnt) 184 { 185 //cout<<cnt<<" "<<rank<<" "<<r->low<<endl; 186 if (r->low+cnt==rank) return r->num; 187 if (r->low+cnt<rank) return Query(r->child[1],rank,r->low+cnt); 188 if (r->low+cnt>rank) return Query(r->child[0],rank,cnt); 189 } 190 int Ask(node* r,double key) 191 { 192 if (my_abs(r->key-key)<=X) return r->low; 193 if (r->key<key) return r->low+Ask(r->child[1],key); 194 if (r->key>key) return Ask(r->child[0],key); 195 } 196 int Count(node* r) 197 { 198 if (!r) return 0; 199 return r->low+Count(r->child[1]); 200 }