关键词：
1861: [Zjoi2006]Book 书架
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 1581 Solved: 884
[Submit][Status][Discuss]
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
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
9
9
7
5
3
HINT
数据范围
id[i]记录编号为i的书在SPLAY中的结点编号,key[i]记录splay中的i结点的书的编号。
splay维护书架上从上到下的书。
TOP：把这本书找到，删掉。然后把最前面的那本书旋转到根，然后把这本书放在根的右儿子。
Bottom类似。
Insert：把这本书找到删掉，然后在相应的位置插入即可。
Ask：旋转到根，查询左儿子的size即可。
Query：用size查找即可。
还有数组要开两倍以上，因为有很多新加结点的操作。
感觉很复杂，调废我。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #define maxn 200010 8 using namespace std; 9 int ch[maxn][2],pre[maxn],size[maxn],key[maxn],id[maxn],tot=0,root=1; 10 char s[10]; 11 inline void Rotate(int x,int kind){ 12 int y=pre[x]; 13 ch[y][!kind]=ch[x][kind]; 14 pre[ch[x][kind]]=y; 15 if(pre[y]) 16 ch[pre[y]][ch[pre[y]][1]==y]=x; 17 pre[x]=pre[y]; 18 ch[x][kind]=y; 19 pre[y]=x; 20 size[y]=size[ch[y][0]]+size[ch[y][1]]+1; 21 size[x]=size[ch[x][0]]+size[ch[x][1]]+1; 22 } 23 inline void splay(int r,int goal){ 24 while(pre[r]!=goal){ 25 if(pre[pre[r]]==goal) 26 Rotate(r,ch[pre[r]][0]==r); 27 else{ 28 int y=pre[r]; 29 int kind=ch[pre[y]][0]==y; 30 if(ch[y][kind]==r){ 31 Rotate(r,!kind); 32 Rotate(r,kind); 33 } 34 else{ 35 Rotate(y,kind); 36 Rotate(r,kind); 37 } 38 } 39 } 40 if(goal==0) root=r; 41 } 42 void newnode(int &x,int fa,int keyy){ 43 x=++tot; 44 pre[x]=fa; 45 size[x]=1; 46 key[x]=keyy; 47 } 48 void query(int x){ 49 int rt=root; 50 while(x){ 51 if(size[ch[rt][0]]+1==x) break; 52 if(size[ch[rt][0]]+1<x) x-=(size[ch[rt][0]]+1),rt=ch[rt][1]; 53 else rt=ch[rt][0]; 54 } 55 printf("%d ",key[rt]); 56 } 57 void top(int x){ 58 int kt=id[x]; 59 splay(kt,0); 60 if(!ch[kt][0]) return; 61 int p1=ch[kt][0]; 62 while(ch[p1][1]) p1=ch[p1][1]; 63 splay(p1,root); 64 if(!ch[kt][1]) root=ch[kt][0],pre[ch[kt][0]]=0; 65 else{ 66 int p2=ch[kt][1]; 67 while(ch[p2][0]) p2=ch[p2][0]; 68 splay(p2,root); 69 pre[p1]=0; 70 pre[p2]=p1; 71 ch[p1][1]=p2; 72 root=p1; 73 } 74 int rt=p1; 75 while(ch[rt][0]) rt=ch[rt][0]; 76 splay(rt,0); 77 newnode(ch[root][0],root,x); 78 size[root]=size[ch[root][0]]+size[ch[root][1]]+1; 79 id[x]=ch[root][0]; 80 } 81 void bottom(int x){ 82 int kt=id[x]; 83 splay(kt,0); 84 if(!ch[kt][1]) return; 85 int p1=ch[kt][1]; 86 while(ch[p1][0]) 87 p1=ch[p1][0]; 88 splay(p1,root); 89 if(!ch[kt][0]) root=ch[kt][1],pre[ch[kt][1]]=0; 90 else{ 91 int p2=ch[kt][0]; 92 while(ch[p2][1]) p2=ch[p2][1]; 93 splay(p2,root); 94 pre[p1]=0; 95 pre[p2]=p1; 96 ch[p1][0]=p2; 97 root=p1; 98 } 99 int rt=p1; 100 while(ch[rt][1]) rt=ch[rt][1]; 101 splay(rt,0); 102 newnode(ch[root][1],root,x); 103 size[root]=size[ch[root][0]]+size[ch[root][1]]+1; 104 id[x]=ch[root][1]; 105 } 106 void Insert(int x){ 107 int k; 108 scanf("%d",&k); 109 if(k==0) return; 110 splay(id[x],0); 111 if(k==1){ 112 int rt=ch[root][1]; 113 if(rt==0) return; 114 while(ch[rt][0]) rt=ch[rt][0]; 115 splay(rt,root); 116 pre[ch[root][1]]=0; 117 pre[ch[root][0]]=ch[root][1]; 118 ch[ch[root][1]][0]=ch[root][0]; 119 root=ch[root][1]; 120 rt=ch[root][1]; 121 size[root]++; 122 if(rt==0) newnode(ch[root][1],root,x),id[x]=ch[root][1]; 123 else{ 124 while(ch[rt][0]) size[rt]++,rt=ch[rt][0]; 125 size[rt]++; 126 newnode(ch[rt][0],rt,x); 127 id[x]=ch[rt][0]; 128 } 129 } 130 else{ 131 int rt=ch[root][0]; 132 if(rt==0) return; 133 while(ch[rt][1]) rt=ch[rt][1]; 134 splay(rt,root); 135 pre[ch[root][0]]=0; 136 pre[ch[root][1]]=ch[root][0]; 137 ch[ch[root][0]][1]=ch[root][1]; 138 root=ch[root][0]; 139 rt=ch[root][0]; 140 size[root]++; 141 if(rt==0) newnode(ch[root][0],root,x),id[x]=ch[root][0]; 142 else{ 143 while(ch[rt][1]) size[rt]++,rt=ch[rt][1]; 144 size[rt]++; 145 newnode(ch[rt][1],rt,x); 146 id[x]=ch[rt][1]; 147 } 148 } 149 } 150 void ask(int x){ 151 int k=id[x]; 152 splay(k,0); 153 printf("%d ",size[ch[k][0]]); 154 } 155 int main() 156 { 157 int n,m,x; 158 scanf("%d%d",&n,&m); 159 scanf("%d",&x); 160 id[x]=1;pre[1]=0; 161 key[1]=x; 162 size[1]=n; 163 for(int i=2;i<=n;i++){ 164 scanf("%d",&x); 165 ch[i-1][1]=i; 166 pre[i]=i-1; 167 size[i]=n-i+1; 168 id[x]=i; 169 key[i]=x; 170 } 171 if(n>2) 172 splay(n/2,0); 173 tot=n; 174 for(int i=1;i<=m;i++){ 175 scanf("%s%d",s,&x); 176 if(s[0]==‘Q‘) query(x); 177 if(s[0]==‘T‘) top(x); 178 if(s[0]==‘B‘) bottom(x); 179 if(s[0]==‘I‘) Insert(x); 180 if(s[0]==‘A‘) ask(x); 181 } 182 return 0; 183 }
bzoj1861:[zjoi2006]book书架
BZOJ1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本... 查看详情
[bzoj1861][zjoi2006]book书架
[BZOJ1861][Zjoi2006]Book书架试题描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一... 查看详情
bzoj1861[zjoi2006]book书架
1#include<bits/stdc++.h>2usingnamespacestd;3constintN=8e4+5;4constintinf=1e9;5intfa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;6voidupdate(intx)7{8size[x]=size[c[x][0]]+size[c[x][1]]+1;9}10voidr 查看详情
bzoj1861:[zjoi2006]book书架
这题想写三次了。结果前两次太困╯﹏╰没写成，大数据结构题就是烦人啊。没什么值得注意的，就按题意一步步来吧。（写了map表示对应树上位置，担心编号大爆掉，不加好像也没啥关系）#include<cstdio>#include<iostream>#i... 查看详情
bzoj1861[zjoi2006]book书架——splay
【题目分析】 模板题目。 首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情
bzoj1861:[zjoi2006]book书架splay
1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情
[zjoi2006]book书架(代码片段)
DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
「luogu2596」[zjoi2006]书架(代码片段)
用平衡树维护每本书的位置1#include<bits/stdc++.h>2usingnamespacestd;3constintN=80010;4intn,m,maxpos,minpos,book[N<<2],bookpos[N];5introot,fa[N<<2],ch[N<<2][2],siz[N<<2],pos[N<<2 查看详情
[zjoi2006]书架(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树 时间复杂度：O(MlogN)[代码] &n 查看详情
[题解]bzoj1861book书架-splay
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
[luogu2596]zjoi2006书架
[Luogu2596]ZJOI2006书架<题目链接>第一次指针写FHQ_Treap（省选噩梦数据结构）AC啦！省选试机写它，紧张过度失败了。省选Day1考场写它，写挂了。省选Day1当晚认真复习它，结果Day2并不考。于是省选后用指针写出来了，开心qwq。... 查看详情
[zjoi2006]书架(代码片段)
[ZJOI2006]书架题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这... 查看详情
题解[zjoi2006]书架（splay）
懒得复制，戳我戳我Solution:还是一个\(Splay\)，我们只用多存一个值\(rad\)来维护二叉树，然后用数组存下每个书对应的值是多少\(Top\)操作，我是把\(s\)旋转到根节点，然后删除，将\(s\)对应的\(rad\)值调至最小，然后插入就可以\(Bot... 查看详情
解题：zjoi2006书架(代码片段)
题面学习了如何在维护序列的平衡树上查找某个数：按初始的顺序定个权值，然后每次找那个权值的DFS序即可。具体实现就是不停往上跳，然后是父亲的右儿子就加上父亲的左儿子，剩下的就是继续熟悉无旋树堆1#include<cstdio&g... 查看详情
bzoj1861:[zjoi2006]book书架（平衡树）(代码片段)
原题链接题目描述：小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些... 查看详情
zjoi2006书架(代码片段)
传送门这道题与普通的(splay)不大相同，别的都是以权值来排序，但这道题是以位置进行排序的，也就是对于一个节点，它的左子树中的节点都在它的上面，右子树中的节点都在他的下面。这个比较独特的一点在于建树，这次不... 查看详情