「BZOJ1861」[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
数据范围
30%的数据，n,m < = 10000
100%的数据，n,m < = 80000
9
9
7
5
3
数据范围
30%的数据，n,m < = 10000
100%的数据，n,m < = 80000
题解
splay还是不熟练，给跪了
唉实在太逗了，这算模板题了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include<iostream> #include<cstdio> #include<cstring> #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,rt,sz; int c[80005][2],fa[80005],deep[80005]; int a[80005],size[80005],v[80005],pos[80005]; void update(int k) { size[k]=size[c[k][0]]+size[c[k][1]]+1; } void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if(c[y][0]==x^c[z][0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); } } void build(int l,int r,int f) { if(l>r)return; int now=l,last=f; if(l==r) { v[now]=a[l];size[now]=1;fa[now]=last; if(l<f)c[last][0]=now; else c[last][1]=now; return; } int mid=(l+r)>>1;now=mid; build(l,mid-1,mid);build(mid+1,r,mid); v[now]=a[mid];fa[now]=last;update(now); if(mid<f)c[last][0]=now; else c[last][1]=now; } int find(int k,int rank) { int l=c[k][0],r=c[k][1]; if(size[l]+1==rank)return k; else if(size[l]>=rank)return find(l,rank); else return find(r,rank-size[l]-1); } void del(int k) { int x,y,z; x=find(rt,k-1);y=find(rt,k+1); splay(x,rt);splay(y,c[x][1]); z=c[y][0];c[y][0]=0;fa[z]=size[z]=0; update(y);update(x); } void move(int k,int val) { int x,y,z=pos[k],rank; splay(z,rt);rank=size[c[z][0]]+1; del(rank); if(val==inf)x=find(rt,n),y=find(rt,n+1); else if(val==-inf)x=find(rt,1),y=find(rt,2); else x=find(rt,rank+val-1),y=find(rt,rank+val); splay(x,rt);splay(y,c[x][1]); size[z]=1;fa[z]=y;c[y][0]=z; update(y);update(x); } int main() { n=read();m=read(); for(int i=2;i<=n+1;i++) a[i]=read(),pos[a[i]]=i; build(1,n+2,0); rt=(3+n)>>1; char ch[10];int S,T; for(int i=1;i<=m;i++) { scanf("%s",ch);S=read(); switch(ch[0]) { case 'T':move(S,-inf);break; case 'B':move(S,inf);break; case 'I':T=read();move(S,T);break; case 'A':splay(pos[S],rt);printf("%d\n",size[c[pos[S]][0]]-1);break; case 'Q':printf("%d\n",v[find(rt,S+1)]);break; } } return 0; } |
计数器 9855316
OI 课件=>
OI 课件=>
大神能解释一下为什么要建立一个虚拟节点吗？
避免边界出现问题