关键词：
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
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
数据范围
Source
题解：
splay模板题练习
代码能力太弱
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> using namespace std; const int N = 2e5 + 20, inf = 2e9; int size[N],fa[N],c[N][2],n,m,sz; int pos[N],a[N],v[N],rt; void push_up(int k) {size[k] = size[c[k][0]] + size[c[k][1]] + 1;} inline 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; push_up(y); push_up(x); } inline void splay(int x,int &k) { while(x != k) { int y = fa[x], z = fa[y]; if(y != k) { if(c[z][0] == y ^ c[y][0] == x) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int &k,int rank) { int l = c[k][0], r = c[k][1]; if(size[l] + 1 == rank) return k; if(size[l] >= rank) return find(l,rank); else return find(r,rank - size[l] - 1); } void change(int S,int T){ if(T == 0) return; int p = pos[S]; splay(p,rt); int rank = size[c[p][0]]; int x = find(rt,size[c[rt][0]]),y = find(rt,size[c[rt][0]]+2); splay(x,rt), splay(y,c[x][1]); c[y][0] = 0;size[c[y][0]] = 0;fa[c[y][0]]=0;push_up(y);push_up(x); if(T == inf) x = find(rt,1), y = find(rt,2); else if(T == -inf) x = find(rt,n),y = find(rt,n+1); else { if(T == 1) x = find(rt,rank+1), y = find(rt,rank+2); else x = find(rt,rank-1), y = find (rt,rank); } splay(x,rt), splay(y,c[x][1]); c[y][0] = p; fa[p] = y; size[p] = 1; push_up(y),push_up(x); } void ins(int &k,int x,int f) { if(k == 0) { k = ++sz; size[k] = 1; v[k] = x; fa[k] = f; return ; } if(x < v[k]) ins(c[k][0],x,k); else ins(c[k][1],x,k); push_up(k); } int main() { scanf("%d%d",&n,&m); for(int i = 2; i <= n+1; ++i) scanf("%d",&a[i]), pos[a[i]] = i; for(int i = 1; i <= n + 2; ++i) ins(rt,i,0),splay(sz,rt); while(m--) { char ch[20];int S,T; scanf("%s%d",ch,&S); if(ch[0] == ‘T‘) change(S,inf);//,cout<<c[c[rt][1]][0]<<endl; if(ch[0] == ‘B‘) change(S,-inf); if(ch[0] == ‘I‘) scanf("%d",&T),change(S,T); if(ch[0] == ‘A‘) splay(pos[S],rt),printf("%d ",size[c[rt][0]] - 1); if(ch[0] == ‘Q‘) printf("%d ",a[find(rt,S+1)]); } return 0; }
[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在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
bzoj1861:[zjoi2006]book书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[题解]bzoj1861book书架-splay
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
bzoj1861：[zjoi2006]书架——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1861（题面复制于洛谷）题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一... 查看详情
[bzoj1861][zjoi2006]书架
BZOJLuoguDescription小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太... 查看详情
[zjoi2006]book书架
pre.cjk{font-family:"DroidSansFallback",monospace}p{margin-bottom:0.25cm;line-height:120%}a:link{}1861:[Zjoi2006]Book书架TimeLimit:4Sec MemoryLimit:64MBSubmit:1581 Solved:884[Submi 查看详情
bzoj1861:[zjoi2006]book书架（平衡树）(代码片段)
原题链接题目描述：小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些... 查看详情
1861.[zjoi2006]书架平衡树-splay(代码片段)
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
[zjoi2006]书架(代码片段)
[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树 时间复杂度：O(MlogN)[代码] &n 查看详情
[zjoi2006]book书架(代码片段)
DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
「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 查看详情
bzoj1861书架splay版
单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情
bzoj1861书架(代码片段)
题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。操作3，其... 查看详情