1861: [Zjoi2006]Book 书架

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 1291  Solved: 741

[][][]

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 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

HINT

 

数据范围

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

 

 

 

Source

分析：

其实就是裸题，对Splay还不是很熟练QAQ

代码：

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 //by NeighThorn  6 using namespace std;  7   8 const int maxn=80000+5;  9  10 int n,m,Min,Max,flag; 11 int root,w[maxn],ls[maxn],rs[maxn],fa[maxn],siz[maxn]; 12  13 char opt[10+5]; 14  15 inline void zig(int x){ 16     int y=fa[x],tmp=siz[y]; 17     if(rs[x]) 18         ls[y]=rs[x],fa[rs[x]]=y,siz[y]=siz[y]-siz[x]+siz[rs[x]],siz[x]=tmp; 19     else  20         ls[y]=0,siz[y]=siz[y]-siz[x],siz[x]=tmp; 21     fa[x]=fa[y]; 22     if(fa[x]){ 23         if(ls[fa[x]]==y) 24             ls[fa[x]]=x; 25         else 26             rs[fa[x]]=x; 27     } 28     fa[y]=x,rs[x]=y; 29 } 30  31 inline void zag(int x){ 32     int y=fa[x],tmp=siz[y]; 33     if(ls[x]) 34         rs[y]=ls[x],fa[ls[x]]=y,siz[y]=siz[y]-siz[x]+siz[ls[x]],siz[x]=tmp; 35     else 36         rs[y]=0,siz[y]=siz[y]-siz[x],siz[x]=tmp; 37     fa[x]=fa[y]; 38     if(fa[x]){ 39         if(ls[fa[x]]==y) 40             ls[fa[x]]=x; 41         else 42             rs[fa[x]]=x; 43     } 44     fa[y]=x,ls[x]=y; 45 } 46  47 inline void splay(int x,int z){ 48     while(fa[x]!=z){ 49         int y=fa[x]; 50         if(fa[y]==z){ 51             if(ls[y]==x) 52                 zig(x); 53             else 54                 zag(x); 55         } 56         else{ 57             if(ls[fa[y]]==y){ 58                 if(ls[y]==x) 59                     zig(y),zig(x); 60                 else 61                     zag(x),zig(x);     62             } 63             else{ 64                 if(rs[y]==x) 65                     zag(y),zag(x); 66                 else 67                     zig(x),zag(x); 68             } 69         } 70     } 71     if(!z) 72         root=x; 73 } 74  75 inline void ins(int rt,int x,int id){ 76     if(!rt) 77         w[id]=x,root=id,siz[id]=1; 78     else if(x
           
            =x)135         return query(ls[rt],x);136     else137         return query(rs[rt],x-siz[ls[rt]]-1);138 }139 140 signed main(void){141 flag=0;142     memset(ls,0,sizeof(ls));143     memset(rs,0,sizeof(rs));144     memset(fa,0,sizeof(fa));145     memset(siz,0,sizeof(siz));146     scanf("%d%d",&n,&m);root=0;Min=1,Max=n;147     for(int i=1,x;i<=n;i++)148         scanf("%d",&x),ins(root,i,x);149     for(int i=1,x,y;i<=m;i++){150         scanf("%s%d",opt,&x);151         if(opt[0]=='T')152             Min--,del(root,x),ins(root,Min,x);153         else if(opt[0]=='B')154             Max++,del(root,x),ins(root,Max,x);155         else if(opt[0]=='I'){156             scanf("%d",&y);splay(x,0);157             if(y==-1){158                 int l=ls[x];159                 while(rs[l])160                     l=rs[l];161                 splay(l,x);int a=w[x],b=w[l];del(root,x),del(root,l);ins(root,b,x),ins(root,a,l);162             }163             else if(y==1){164                 int r=rs[x];165                 while(ls[r])166                     r=ls[r];167                 splay(r,x);int a=w[x],b=w[r];del(root,x),del(root,r);ins(root,b,x),ins(root,a,r);168             }169         }170         else if(opt[0]=='A')171             printf("%d\n",rank(root,x)-1);172         else173             printf("%d\n",query(root,x));174     }175     return 0;176 }
           
          
         
        
       

---

by NeighThorn