1861: [Zjoi2006]Book 书架
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
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
9
9
7
5
3
HINT
数据范围
100%的数据，n,m < = 80000
Splay
#include<cstdio>
#define MaxN 80010
int N,M,tot,root,t;
int A[MaxN],Q[MaxN];
struct point{
int fa,d,key,size;
int son[2];
point(){
size=son[0]=son[1]=0;
}
}P[MaxN];
void New(int &x,int fa,int d,int key){
if (t) {
x=t;
t=0;
}
else x=++tot;
P[x].fa=fa;
P[x].d=d;
P[x].key=key;
P[x].size=1;
P[x].son[0]=P[x].son[1]=0;
Q[key]=x;
}
void Up(int k){
P[k].size=P[P[k].son[0]].size+P[P[k].son[1]].size+1;
}
void Build(int l,int r,int &x,int fa,int d){
if (l>r) return;
int mid=(l+r)/2;
New(x,fa,d,A[mid]);
Build(l,mid-1,P[x].son[0],x,0);
Build(mid+1,r,P[x].son[1],x,1);
Up(x);
}
void Turn(int x){
int y=P[x].fa; int dx=P[x].d;
int z=P[y].fa; int dy=P[y].d;
P[x].d=dy; P[x].fa=z;
if (z) P[z].son[dy]=x;
dy=1-dx; z=P[x].son[dy];
P[y].d=dy; P[y].fa=x; P[x].son[dy]=y;
P[z].d=dx; P[z].fa=y; P[y].son[dx]=z;
Up(y); Up(x);
}
void Splay(int x,int fa){
for (;P[x].fa!=fa;){
if (P[P[x].fa].fa!=fa){
if (P[x].d==P[P[x].fa].d) Turn(P[x].fa);
else Turn(x);
}
if (P[x].fa==fa) break;
Turn(x);
}
if (!fa) root=x;
}
void Delete(int x){
t=x;
Splay(x,0);
int l=P[x].son[0],r=P[x].son[1];
P[l].d=P[r].d=2;
P[l].fa=P[r].fa=0;
if (!l ||!r ){
root=l?l:r;
return;
}
for (;P[l].son[1];l=P[l].son[1]);
for (;P[r].son[0];r=P[r].son[0]);
Splay(l,0);
Splay(r,0);
P[l].son[1]=r;
P[r].d=1;
P[r].fa=l;
root=l;
Up(l);
}
int find(int k){
int u=root;
int s=0;
for (;;){
if (P[P[u].son[0]].size+s+1==k) return u;
if (P[P[u].son[0]].size+s+1<k){
s+=P[P[u].son[0]].size+1;
u=P[u].son[1];
}
else u=P[u].son[0];
}
}
int Sum(int k){
Splay(k,0);
return P[P[k].son[0]].size+1;
}
void Insert(int pos,int i){
int u1=find(pos);
int u2=find(pos+1);
Splay(u1,0);
Splay(u2,u1);
New(P[u2].son[0],u2,0,i);
for (int x=u2;x;x=P[x].fa)
P[x].size++;
}
void Cout(int u){
if (!u) return;
Cout(P[u].son[0]);
printf("^%d ",P[u].key);
Cout(P[u].son[1]);
}
int main(){
scanf("%d%d",&N,&M);
for (int i=1;i<=N;++i)
scanf("%d",&A[i]);
Build(0,N+1,root,0,2);
char s[10];
for (;M--;){
scanf("%s",s);
int x;
scanf("%d",&x);
if (s[0]=='T'){
Delete(Q[x]);
Insert(1,x);
}
if (s[0]=='B'){
Delete(Q[x]);
Insert(N,x);
}
if (s[0]=='I'){
int l;
scanf("%d",&l);
if (!l) continue;
l=l+Sum(Q[x])-1;
Delete(Q[x]);
Insert(l,x);
}
if (s[0]=='A')
printf("%d\n",Sum(Q[x])-2);
if (s[0]=='Q')
printf("%d\n",P[find(x+1)].key);
}
}
评论 (0)
