[ZJOI2006]书架

题目描述

小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的下標表示pos,大小關係表示位置。

對於Top和Bottom，我們把x旋到根，再把左兒子接到右兒子上或相反。

對於ins 我們把x的上（下）一個位置轉到根，再把x取下來接到對面子樹。

細節很多！！

註意事項：

1.修改完要一整條鏈維護。

2.刪除x時要把x的兒子接到x的父親上。

3.父子關係要成對修改。

4.沒有節點的情況

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 int n,m,pos[100005],rt;
  9 struct node{
 10     int ch[2],f,x,sz;
 11 }tr[100005];
 12 void wh(int k){
 13     tr[k].sz=tr[tr[k].ch[0]].sz+tr[tr[k].ch[1]].sz+1;
 14 }
 15 void print_a(int x){
 16     if(!x)return;
 17     print_a(tr[x].ch[0]);
 18     printf("%d ",x);
 19     print_a(tr[x].ch[1]);
 20 }
 21 int build(int f,int l,int r){
 22     if(l>r)return 0;
 23     int mid=l+r>>1;
 24     int k=pos[mid];
 25     tr[k].x=mid;tr[k].sz=1;
 26     tr[k].f=f;
 27     tr[k].ch[0]=build(k,l,mid-1);
 28     tr[k].ch[1]=build(k,mid+1,r);
 29     wh(k);
 30     //printf("k=%d p=%d sz=%d f=%d ls=%d rs=%d
",k,tr[k].x,tr[k].sz,tr[k].f,tr[k].ch[0],tr[k].ch[1]);
 31     return k;
 32 }
 33 bool get(int x){
 34     return tr[tr[x].f].ch[1]==x;
 35 }
 36 void rotate(int x){
 37     int y=tr[x].f,z=tr[y].f;
 38     int wx=get(x),wy=get(y);
 39     tr[z].ch[wy]=x;tr[x].f=z;
 40     tr[y].ch[wx]=tr[x].ch[wx^1];tr[tr[x].ch[wx^1]].f=y;
 41     tr[x].ch[wx^1]=y;tr[y].f=x;
 42     wh(y);wh(x);
 43 }
 44 void splay(int x,int g){
 45     while(tr[x].f!=g){
 46         int y=tr[x].f,z=tr[y].f;
 47         if(z!=g)rotate((get(x)==get(y))?y:x);
 48         rotate(x);
 49     }
 50     if(!g)rt=x;
 51 }
 52 void Top(int x){
 53     splay(x,0);
 54     int t1=tr[rt].ch[0];
 55     int t2=tr[rt].ch[1];
 56     if(!t1)return;
 57     if(!t2){swap(tr[rt].ch[0],tr[rt].ch[1]);return;}
 58     while(tr[t2].ch[0])t2=tr[t2].ch[0];
 59     tr[rt].ch[0]=0;
 60     tr[t2].ch[0]=t1;tr[t1].f=t2;
 61     for(int i=t1;i;i=tr[i].f)wh(i);
 62 }
 63 void Bottom(int x){
 64     splay(x,0);
 65     int t1=tr[rt].ch[0];
 66     int t2=tr[rt].ch[1];
 67     if(!t2)return;
 68     if(!t1){swap(tr[rt].ch[0],tr[rt].ch[1]);return;}
 69     while(tr[t1].ch[1])t1=tr[t1].ch[1];
 70     tr[rt].ch[1]=0;
 71     tr[t1].ch[1]=t2;tr[t2].f=t1;
 72     for(int i=t2;i;i=tr[i].f)wh(i);
 73 }
 74 int kth(int x){
 75     int k=rt;
 76     //cout<<x<<' '<<k<<' '<<tr[k].sz<<endl;
 77     while(1){
 78         int ls=tr[k].ch[0];
 79         if(tr[ls].sz>=x)k=ls;
 80         else if(tr[ls].sz==x-1)return k;
 81         else x-=tr[ls].sz+1,k=tr[k].ch[1];
 82     }
 83 }
 84 
 85 int find(int x){
 86     splay(x,0);
 87     return tr[tr[rt].ch[0]].sz+1;
 88 }
 89 void Ins(int x,int y){
 90     if(!y)return;
 91     int p=kth(find(x)+y);splay(p,0);
 92     if(y>0){
 93     //    cout<<rt<<endl;
 94         int wx=get(x);
 95         tr[tr[x].f].ch[wx]=tr[x].ch[wx];tr[tr[x].ch[wx]].f=tr[x].f;
 96         tr[x].ch[wx]=0;
 97         for(int i=tr[x].f;i;i=tr[i].f)wh(i);
 98         int t=tr[rt].ch[1];
 99         
100         //print_a(rt);puts("");
101         if(!t){
102             tr[rt].ch[1]=x;tr[x].f=rt;
103             wh(x);wh(rt);
104         }
105         else{
106             while(tr[t].ch[0])t=tr[t].ch[0];
107             tr[t].ch[0]=x;tr[x].f=t;
108             for(int i=x;i;i=tr[i].f)wh(i);
109         }
110     }
111     else {
112         //cout<<rt<<endl;
113         int wx=get(x);
114         tr[tr[x].f].ch[wx]=tr[x].ch[wx];tr[tr[x].ch[wx]].f=tr[x].f;
115         tr[x].ch[wx]=0;
116         for(int i=tr[x].f;i;i=tr[i].f)wh(i);
117         //print_a(rt);puts("");
118         int t=tr[rt].ch[0];
119         if(!t){
120             tr[rt].ch[0]=x;tr[x].f=rt;
121             wh(x);wh(rt);
122         }
123         else{
124             while(tr[t].ch[1])t=tr[t].ch[1];
125             tr[t].ch[1]=x;tr[x].f=t;
126             for(int i=x;i;i=tr[i].f)wh(i);
127             //print_a(rt);puts("");
128         }
129     }
130 }
131 void ask(int x){
132     int k=find(x);
133     printf("%d
",k-1);
134 }
135 void query(int x){
136      int t=kth(x);
137     //print_a(rt);puts("");
138      printf("%d
",t);
139 }
140 int main(){
141     cin>>n>>m;
142     for(int i=1;i<=n;i++)scanf("%d",&pos[i]);
143     rt=build(0,1,n);
144     while(m--){
145         char ch[8];int x,y;
146         scanf("%s %d",ch,&x);
147         if(ch[0]=='T')Top(x);
148         if(ch[0]=='B')Bottom(x);
149         if(ch[0]=='I'){
150             scanf("%d",&y);
151             Ins(x,y);
152         }
153         if(ch[0]=='A')ask(x);
154         if(ch[0]=='Q')query(x);
155     }
156     return 0;
157 }

View Code