小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语句你应该输出一行，一个数，代表询问的答案。
题解：
题目要求支持在数列中移动、询问元素，平衡树毫无疑问可以解决这种问题。但是，区间线段树也可以解决这个问题。
每个线段树节点记录对应的区间里有多少本书，则询问操作变成了单点访问、区间求和。
因为该题的操作只有交换相邻、把某个元素放到最前、把某个元素放到最后三种，所有书所占用的区间左右段点最多向外移动m，可以开n+2*m的区间来解决。
注意记录每本书在哪个位置、某个位置有什么书，移动时记得更新。
代码：
var i,j,k,l,y,n,m,ls,rs,cnt:longint; t:array[0..500000,-2..2]of longint; wz,bh:array[0..250000]of longint; ch,ch2:char; procedure build(l,r,fa:longint); var x:longint; begin inc(cnt); x:=cnt; t[x,1]:=l; t[x,2]:=r; if t[x,1]=t[fa,1] then t[fa,-1]:=x else t[fa,-2]:=x; if l=r then begin if bh[l]>0 then t[x,0]:=1; exit; end; build(l,(l+r)div 2,x); build((l+r)div 2+1,r,x); t[x,0]:=t[t[x,-1],0]+t[t[x,-2],0]; end; procedure work(x,y,z:longint); begin t[x,0]:=t[x,0]+z; if t[x,1]=t[x,2] then exit; if y<=(t[x,1]+t[x,2])div 2 then work(t[x,-1],y,z) else work(t[x,-2],y,z); end; function qq(x,l,r:longint):longint; var ll,rr:longint; begin if(t[x,1]=l)and(t[x,2]=r)then exit(t[x,0]); ll:=t[x,1]; rr:=t[x,2]; if r<=(ll+rr)div 2 then exit(qq(t[x,-1],l,r)) else if l>(ll+rr)div 2 then exit(qq(t[x,-2],l,r))else exit(qq(t[x,-1],l,(ll+rr)div 2)+qq(t[x,-2],(ll+rr)div 2+1,r)); end; function qq2(y:longint):longint; var k,l:longint; begin k:=1; while t[k,1]<>t[k,2] do begin l:=t[k,-1]; if t[l,0]>=y then k:=l else begin y:=y-t[l,0]; k:=t[k,-2]; end; end; exit(bh[t[k,1]]); end; begin readln(n,m); for i:=1 to n do begin read(j); bh[i+80000]:=j; wz[j]:=i+80000; end; readln; ls:=80000; rs:=80000+n+1; build(0,80000+n+80000,0); for i:=1 to m do begin read(ch); read(ch2); while ch2<>‘ ‘ do read(ch2); if ch=‘Q‘ then begin readln(j); writeln(qq2(j)); end else if ch=‘T‘ then begin readln(j); work(1,wz[j],-1); work(1,ls,1); bh[wz[j]]:=0; wz[j]:=ls; bh[ls]:=j; dec(ls); end else if ch=‘B‘ then begin readln(j); work(1,wz[j],-1); work(1,rs,1); bh[wz[j]]:=0; wz[j]:=rs; bh[rs]:=j; inc(rs); end else if ch=‘A‘ then begin readln(j); writeln(qq(1,0,wz[j]-1)); end else begin readln(j,k); if k=0 then continue; l:=qq(1,0,wz[j]); l:=qq2(l+k); y:=wz[j]; wz[j]:=wz[l]; wz[l]:=y; y:=bh[wz[j]]; bh[wz[j]]:=bh[wz[l]]; bh[wz[l]]:=y; end; end; end.
原文：http://www.cnblogs.com/GhostReach/p/6262515.html
