题目描述
小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);PRintf("%d/n",tree.ask(x));} else{scanf("%d",&x);printf("%d/n",tree.query(x));} } return 0;}^_^
新闻热点
疑难解答
