首页 > 代码库 > wikioi 1514 and ZJOI2006 书架
wikioi 1514 and ZJOI2006 书架
1514 书架
题目描述 Description
小 T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 1 到 n 的正整数给每本书都编了号。
小 T 在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小 T 的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有 X 本书，那么放回去时这本书上面就只可能有 X-1、X或 X+1 本书。
当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时
候粗心的小 T 会随手把书放在书柜里所有书的最上面或者最下面，然后转身离
开。
久而久之，小 T 的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为 X 的书在书柜的什么位置；(2)从上到下第 i 本书的编号是多少。
输入描述 Input Description
第一行有两个数 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 Description
对于每一条 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
数据范围及提示 Data Size & Hint
30%的数据，n,m<=10000
100%的数据，n,m<=80000
题解：
神奇的splay！
我觉得刚开始的时候以序号按BST建树，
建好树之后在删除、加入的时候只是人为定义它的位置或者rank，
它的编号已经不代表什么了，而它的编号因为一直不变所以可以为我们做一些事情，比如本题
因此splay也可以回收废节点
。。。语言表达能力有限。。。
哪里说得不对请神牛指出
代码：
1 const maxn=80000+100;inf=maxlongint>>1; 2 var i,n,m,x,t,rt:longint; 3 ch:char; 4 s,pos,v,fa,a:array[0..maxn] of longint; 5 c:array[0..maxn,0..1] of longint; 6 procedure pushup(x:longint); 7 begin 8 s[x]:=s[c[x,0]]+s[c[x,1]]+1; 9 end; 10 procedure rotate(x:longint;var k:longint); 11 var l,r,y,z:longint; 12 begin 13 y:=fa[x];z:=fa[y]; 14 l:=ord(c[y,1]=x);r:=l xor 1; 15 if y=k then k:=x else c[z,ord(c[z,1]=y)]:=x; 16 fa[x]:=z;fa[y]:=x;fa[c[x,r]]:=y; 17 c[y,l]:=c[x,r];c[x,r]:=y; 18 pushup(y);pushup(x); 19 end; 20 procedure splay(x:longint;var k:longint); 21 var y,z:longint; 22 begin 23 while x<>k do 24 begin 25 y:=fa[x];z:=fa[y]; 26 if y<>k then 27 if (c[z,0]=y) xor (c[y,0]=x) then rotate(x,k) 28 else rotate(y,k); 29 rotate(x,k); 30 end; 31 end; 32 function find(x,rank:longint):longint; 33 var l,r:longint; 34 begin 35 l:=c[x,0];r:=c[x,1]; 36 if s[l]+1=rank then exit(x) 37 else if s[l]>=rank then exit(find(l,rank)) 38 else exit(find(r,rank-s[l]-1)); 39 end; 40 procedure del(k:longint); 41 var x,y,z:longint; 42 begin 43 x:=find(rt,k-1);y:=find(rt,k+1); 44 splay(x,rt);splay(y,c[x,1]); 45 z:=c[y,0];fa[z]:=0;s[z]:=0;c[y,0]:=0; 46 pushup(y);pushup(x); 47 end; 48 49 procedure build(l,r,f:longint); 50 var mid,now,last:longint; 51 begin 52 if l>r then exit; 53 mid:=(l+r)>>1; 54 now:=mid;last:=f; 55 fa[now]:=last;v[now]:=a[mid]; 56 c[last,ord(mid>f)]:=now; 57 if l=r then 58 begin 59 s[now]:=1; 60 exit; 61 end; 62 build(l,mid-1,mid);build(mid+1,r,mid); 63 pushup(now); 64 end; 65 66 procedure init; 67 begin 68 readln(n,m); 69 for i:=2 to n+1 do read(a[i]);readln; 70 for i:=2 to n+1 do pos[a[i]]:=i; 71 build(1,n+2,0);rt:=(n+3)>>1; 72 end; 73 procedure move(k,val:longint); 74 var x,y,z,rank:longint; 75 begin 76 if val=0 then exit; 77 z:=pos[k];splay(z,rt);rank:=s[c[z,0]]+1;del(rank); 78 if val=inf then begin x:=find(rt,n);y:=find(rt,n+1);end 79 else if val=-inf then begin x:=find(rt,1);y:=find(rt,2);end 80 else begin x:=find(rt,rank+val-1);y:=find(rt,rank+val);end; 81 splay(x,rt);splay(y,c[x,1]); 82 fa[z]:=y;s[z]:=1;c[y,0]:=z; 83 pushup(y);pushup(x); 84 end; 85 procedure main; 86 begin 87 for i:=1 to m do 88 begin 89 read(ch); 90 case ch of 91 ‘T‘:begin 92 while ch<>‘ ‘ do read(ch); 93 readln(x);move(x,-inf); 94 end; 95 ‘B‘:begin 96 while ch<>‘ ‘ do read(ch); 97 readln(x);move(x,inf); 98 end; 99 ‘I‘:begin100 while ch<>‘ ‘ do read(ch);101 readln(x,t);move(x,t);102 end;103 ‘A‘:begin104 while ch<>‘ ‘ do read(ch);105 readln(x);106 splay(pos[x],rt);writeln(s[c[rt,0]]-1);107 end;108 ‘Q‘:begin109 while ch<>‘ ‘ do read(ch);110 readln(x);111 writeln(v[find(rt,x+1)]);112 end;113 end;114 end;115 end;116 begin117 assign(input,‘input.txt‘);assign(output,‘output.txt‘);118 reset(input);rewrite(output);119 init;120 main;121 close(input);close(output);122 end.123