【BZOJ 1861】 [Zjoi2006]Book 书架

1861: [Zjoi2006]Book 书架Time Limit:4 SecMemory Limit:64 MBSubmit:639Solved:372[Submit][Status]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 101 3 2 7 5 8 10 4 9 6Query 3 Top 5 Ask 6 Bottom 3 Ask 3 Top 6 Insert 4 -1 Query 5 Query 2 Ask 2

Sample Output

299753

HINT

数据范围

100%的数据，n,m < = 80000

Source

Day2

以位置为关键字的splay模板题。

先按照读入建出splay，并且记录每个编号的书对应在splay上的结点是哪个。

移动操作可以统一成一种Move(x,y)把编号x的点移动到第y个位置上，我们只要先删掉这个点再加入即可。

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>#define M 100005using namespace std;struct splay{int l,r,size,fa,v;}a[M];int id[M],v[M],tot,n,m,root;char str[50];void Push_up(int x){if (!x) return;a[x].size=a[a[x].l].size+a[a[x].r].size+1;}void zig(int x){int y=a[x].fa;int z=a[y].fa;a[x].fa=z,a[y].fa=x;a[y].l=a[x].r,a[a[x].r].fa=y,a[x].r=y;if (a[z].l==y) a[z].l=x;else a[z].r=x;Push_up(y);}void zag(int x){int y=a[x].fa;int z=a[y].fa;a[x].fa=z,a[y].fa=x;a[y].r=a[x].l,a[a[x].l].fa=y,a[x].l=y;if (a[z].l==y) a[z].l=x;else a[z].r=x;Push_up(y);}void splay(int x,int s){while (a[x].fa!=s){int y=a[x].fa;int z=a[y].fa;if (z==s){if (x==a[y].l) zig(x);else zag(x);break;}if (y==a[z].l){if (x==a[y].l)zig(y),zig(x);else zag(x),zig(x);}else {if (x==a[y].r)zag(y),zag(x);else zig(x),zag(x);}}Push_up(x);if (!s) root=x;}void New_node(int &x,int fa,int k){x=++tot;a[x].l=a[x].r=0;a[x].fa=fa;a[x].v=k;a[x].size=1;}void Build(int &x,int fa,int l,int r){if (l>r) return;int m=(l+r)>>1;New_node(x,fa,v[m]);id[v[m]]=x;Build(a[x].l,x,l,m-1);Build(a[x].r,x,m+1,r);Push_up(x);}int Findkth(int x,int k){int ls=a[a[x].l].size;if (ls+1==k) return x;if (ls>=k) return Findkth(a[x].l,k);return Findkth(a[x].r,k-ls-1);}void Move(int x,int tar){//deletesplay(x,0);int pre=Findkth(root,a[a[x].l].size),ne=Findkth(root,a[a[x].l].size+2);splay(pre,0),splay(ne,root);a[ne].l=0,a[x].fa=0;splay(ne,0);//insertpre=Findkth(root,tar-1),ne=Findkth(root,tar);splay(pre,0),splay(ne,root);a[ne].l=x,a[x].fa=ne;splay(x,0);}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&v[i]);v[0]=v[n+1]=0;Build(root,0,0,n+1);while (m–){int k,T;scanf("%s%d",str,&k);if (str[0]=='T'){Move(id[k],1+1);}if (str[0]=='B'){Move(id[k],n+1);}if (str[0]=='I'){scanf("%d",&T);splay(id[k],0);Move(id[k],a[a[root].l].size+1+T);}if (str[0]=='A'){splay(id[k],0);printf("%d\n",a[a[root].l].size-1);}if (str[0]=='Q'){printf("%d\n",a[Findkth(root,k+1)].v);}}return 0;}

大把大把的时光从指缝间遛走，