关键词：
这道题与普通的(splay)不大相同，别的都是以权值来排序，但这道题是以位置进行排序的，也就是对于一个节点，它的左子树中的节点都在它的上面，右子树中的节点都在他的下面。
这个比较独特的一点在于建树，这次不能再二分查找要插入的位置了，而是每一次直接把当前插入的点作为上一次插入的点的右儿子（符合上面说的性质），然后(splay)一下就好了。
至于置顶和置底操作，实际上就相当于把它的左/右子树合并到它的后继/前驱上，这个还是很简单的。
放书操作的话就是找到前驱和后继然后直接交换它们的值。
(ask)操作就把要找的那个点(splay)到根之后输出其左子树大小，求排名的话就像(BST)一样了。
注意因为本题平衡树是以位置来排序，但是我们在找的时候不能通过(BST)的方法找到，所以我们还记录一下(pos_i)表示位置为(i)的书在树上的编号。（这个在执行过插入操作之后就不会变了），这样就可以了。
一直没(debug)出来竟然是因为多打了一个按位异或……
看一下代码。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar(‘
‘)
#define de putchar(‘#‘)
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
const int M = 100005;
const int N = 10000005;
const int INF = 1000000009;
int read()
int ans = 0,op = 1;
char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘)
if(ch == ‘-‘) op = -1;
ch = getchar();
while(ch >=‘0‘ && ch <= ‘9‘)
ans *= 10;
ans += ch - ‘0‘;
ch = getchar();
return ans * op;
struct node
int fa,ch[2],son,cnt,val;
t[M<<1];
int n,m,idx,tot,x,pos[M<<1],root,a;
char s[10];
bool get(int x)
return t[t[x].fa].ch[1] == x;
void pushup(int x)
t[x].son = t[t[x].ch[0]].son + t[t[x].ch[1]].son + t[x].cnt;
void rotate(int x)
int y = t[x].fa,z = t[y].fa,k = get(x);
t[z].ch[t[z].ch[1] == y] = x,t[x].fa = z;
t[y].ch[k] = t[x].ch[k^1],t[t[y].ch[k]].fa = y;
t[x].ch[k^1] = y,t[y].fa = x;
pushup(x),pushup(y);
void splay(int x,int goal)
while(t[x].fa != goal)
int y = t[x].fa,z = t[y].fa;
if(z != goal) (t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);
rotate(x);
if(!goal) root = x;
//pos[t[x].val] = x;
void insert(int x)
int u = ++idx;
t[u].val = x,pos[x] = u;
t[u].son = t[u].cnt = 1;
t[u].ch[0] = t[u].ch[1] = 0;
if(u > 1) t[u-1].ch[1] = u,t[u].fa = u-1,splay(u,0);
void change(int x,int p)
splay(pos[x],0);
if(!t[root].ch[p]) return;
if(!t[root].ch[p^1]) t[root].ch[p^1] = t[root].ch[p],t[root].ch[p] = 0;
else
int g = t[root].ch[p^1];
while(t[g].ch[p]) g = t[g].ch[p];
t[t[root].ch[p]].fa = g,t[g].ch[p] = t[root].ch[p],t[root].ch[p] = 0;
splay(t[g].ch[p],0);
void modify(int x,int f)
splay(pos[x],0);
if(f == 0) return;
else if(f == 1)
int g = t[root].ch[1],p = pos[x];
while(t[g].ch[0]) g = t[g].ch[0];
swap(pos[x],pos[t[g].val]);
swap(t[p].val,t[g].val);
else if(f == -1)
int g = t[root].ch[0],p = pos[x];
while(t[g].ch[1]) g = t[g].ch[1];
swap(pos[x],pos[t[g].val]);
swap(t[p].val,t[g].val);
void ask(int x)
splay(pos[x],0);
printf("%d
",t[t[root].ch[0]].son);
int rk(int x)
int u = root;
while(1)
int y = t[u].ch[0];
if(x <= t[y].son) u = y;
else if(x > t[y].son + t[u].cnt) x -= (t[y].son + t[u].cnt),u = t[u].ch[1];
else return t[u].val;
int main()
//pos[0] = t[0].son = t[0].cnt = t[0].ch[1] = t[0].ch[0] = t[0].fa = t[0].val = 0;
n = read(),m = read();
rep(i,1,n) x = read(),insert(x);
rep(i,1,m)
scanf("%s",s);
if(s[0] == ‘T‘) x = read(),change(x,0);
else if(s[0] == ‘B‘) x = read(),change(x,1);
else if(s[0] == ‘I‘) x = read(),a = read(),modify(x,a);
else if(s[0] == ‘A‘) x = read(),ask(x);
else if(s[0] == ‘Q‘) x = read(),printf("%d
",rk(x));
return 0;
解题：zjoi2006书架(代码片段)
题面学习了如何在维护序列的平衡树上查找某个数：按初始的顺序定个权值，然后每次找那个权值的DFS序即可。具体实现就是不停往上跳，然后是父亲的右儿子就加上父亲的左儿子，剩下的就是继续熟悉无旋树堆1#include<cstdio&g... 查看详情
「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书架(代码片段)
传送门这道题与普通的(splay)不大相同，别的都是以权值来排序，但这道题是以位置进行排序的，也就是对于一个节点，它的左子树中的节点都在它的上面，右子树中的节点都在他的下面。这个比较独特的一点在于建树，这次不... 查看详情
[zjoi2006]书架(代码片段)
题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
[zjoi2006]book书架(代码片段)
DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情
☆[zjoi2006]书架「平衡树维护数列」(代码片段)
题目类型：平衡树传送门：>Here<题意：要求维护一个数列，支持：将某个元素置顶或置底，交换某元素与其前驱或后继的位置，查询编号为(S)的元素的排名，查询排名第(k)的元素编号解题思路可以说是平衡树维护数列的入门... 查看详情
p2596[zjoi2006]书架(代码片段)
\\(\\colorpurple\\textP2596[ZJOI2006]书架\\)解题方法考虑使用\\(\\textFHQ\\)平衡树，我们只使用编号，而不使用权值，平衡树上的先序遍历即为书的放置顺序。\\(\\textQuery\\)：这是最简单的操作，直接查询即可。\\(\\textAsk\\)：本题的核心，... 查看详情
1861.[zjoi2006]书架平衡树-splay(代码片段)
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情
洛谷p2596[zjoi2006]书架splay(代码片段)
题目描述小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书架——splay
【题目分析】 模板题目。 首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情
bzoj1861:[zjoi2006]book书架（splay）
1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1453 Solved: 822[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到 查看详情
[luogu2596]zjoi2006书架
[Luogu2596]ZJOI2006书架<题目链接>第一次指针写FHQ_Treap（省选噩梦数据结构）AC啦！省选试机写它，紧张过度失败了。省选Day1考场写它，写挂了。省选Day1当晚认真复习它，结果Day2并不考。于是省选后用指针写出来了，开心qwq。... 查看详情
题解[zjoi2006]书架（splay）
懒得复制，戳我戳我Solution:还是一个\(Splay\)，我们只用多存一个值\(rad\)来维护二叉树，然后用数组存下每个书对应的值是多少\(Top\)操作，我是把\(s\)旋转到根节点，然后删除，将\(s\)对应的\(rad\)值调至最小，然后插入就可以\(Bot... 查看详情
[zjoi2006]书架（权值splay）(代码片段)
[ZJOI2006]书架（luogu）Description题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿... 查看详情
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 查看详情