題目描述
小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語句你應該輸出一行，一個數，代表詢問的答案。
分析： Splay模板題，注意編號與Splay序列里的對應關系。 具體而言： 1.top相當于把結點旋轉到根，再把左子樹接到右子樹上，bottom類似 2.insert相當于把結點與相應的前面一個（或后面）交換 3.對于ask，我們把x提到根，那么左子樹的size即為答案；對于query，則是詢問splay里第k本書的編號。
錯誤集錦： 1.一開始建splay時，把書的編號與在序列中的順序弄混了 2.有許多地方需要把變量a賦值給b，但在賦值前就已經改變了a的值了 3.在swap函數中沒有打&（那不就什么都沒換嗎，，，但樣例竟然對了 qnq）
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int maxn=80010;int n,m;struct Splay{ int ch[maxn][2]; int size[maxn],pos[maxn],val[maxn]; int fa[maxn]; int rt; int cnt; void init(){ rt=cnt=0; } void swp(int& a,int& b){ a^=b^=a^=b; } void maintain(int x){ size[x]=1; if(ch[x][0]) size[x]+=size[ch[x][0]];if(ch[x][1]) size[x]+=size[ch[x][1]]; } void rotate(int x){ int y=fa[x],z=fa[y]; int l=(x==ch[y][1]); if(z) ch[z][y==ch[z][1]]=x; fa[x]=z; fa[y]=x;fa[ch[x][l^1]]=y; ch[y][l]=ch[x][l^1];ch[x][l^1]=y; maintain(y); } void splay(int x,int aim){ while(fa[x]!=aim){ int y=fa[x],z=fa[y]; if(fa[y]!=aim){ if((x==ch[y][0]) ^ (y==ch[z][0]))rotate(x); else rotate(y); } rotate(x); } maintain(x); if(aim==0) rt=x; } void insert(int v){ int x=rt; while(ch[x][1]) x=ch[x][1]; ch[x][1]=++cnt;fa[cnt]=x; pos[v]=cnt;val[cnt]=v; splay(cnt,0);// } void top_bot(int x,int l){ splay(pos[x],0); if(!ch[rt][l]) return; if(!ch[rt][l^1]){ch[rt][l^1]=ch[rt][l];ch[rt][l]=0;return;}// int t=ch[rt][l^1]; while(ch[t][l]) t=ch[t][l]; fa[ch[rt][l]]=t,ch[t][l]=ch[rt][l],ch[rt][l]=0; splay(ch[t][l],0); } void ist(int x,int p){ splay(pos[x],0); if(!p) return; if(p==1){ int t=rt,ps=pos[x]; t=ch[t][1]; while(ch[t][0]) t=ch[t][0]; swp(pos[x],pos[val[t]]);swp(val[ps],val[t]); }else{ int t=rt,ps=pos[x]; t=ch[t][0]; while(ch[t][1]) t=ch[t][1]; swp(pos[x],pos[val[t]]);swp(val[ps],val[t]); } } int ask(int x){ splay(pos[x],0); return size[ch[rt][0]]; } int query(int x){ int u=rt; while(1){ if(size[ch[u][0]]+1==x)return val[u]; if(size[ch[u][0]]>=x) u=ch[u][0]; else x-=size[ch[u][0]]+1,u=ch[u][1]; } }}tree;int main(){ scanf("%d%d",&n,&m); tree.init(); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); tree.insert(x); } for(int i=1;i<=m;i++){ char s[10];int x,y; scanf("%s",s); if(s[0]=='T'){scanf("%d",&x);tree.top_bot(x,0);} else if(s[0]=='B'){scanf("%d",&x);tree.top_bot(x,1);} else if(s[0]=='I'){scanf("%d%d",&x,&y);tree.ist(x,y);} else if(s[0]=='A'){scanf("%d",&x);^_^新聞熱點
疑難解答
