关键词：
[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1861
[算法]
平衡树
时间复杂度 ： O(M log N)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 800010 int n,m; int a[MAXN]; struct Splay int root , total; int pos[MAXN]; Splay() root = total = 0; memset(pos,0,sizeof(pos)); struct Node int fa; int value,size; int son[2]; Tree[MAXN]; inline bool get(int x) return Tree[Tree[x].fa].son[1] == x; inline void splay(int x) for (int fa = Tree[x].fa; (fa = Tree[x].fa); rotate(x)) rotate(get(x) == get(fa) ? fa : x); root = x; inline void push_back(int x) if (!root) root = pos[x] = ++total; Tree[root].fa = 0; Tree[root].son[0] = Tree[root].son[1] = 0; Tree[root].value = x; Tree[root].size = 1; return; int now = root; while (Tree[now].son[1]) now = Tree[now].son[1]; Tree[now].son[1] = pos[x] = ++total; Tree[total].fa = now; Tree[total].son[0] = Tree[total].son[1] = 0; Tree[total].value = x; Tree[total].size = 1; splay(total); inline void update(int x) Tree[x].size = 1; Tree[x].size += Tree[Tree[x].son[0]].size; Tree[x].size += Tree[Tree[x].son[1]].size; inline void rotate(int x) int f = Tree[x].fa , g = Tree[f].fa; int tmpx = get(x) , tmpf = get(f); if (!f) return; Tree[f].son[tmpx] = Tree[x].son[tmpx ^ 1]; if (Tree[x].son[tmpx ^ 1]) Tree[Tree[x].son[tmpx ^ 1]].fa = f; Tree[x].son[tmpx ^ 1] = f; Tree[f].fa = x; if (g) Tree[g].son[tmpf] = x; Tree[x].fa = g; update(f); update(x); inline int find(int x) int now = root; while (now) if (Tree[now].son[0] && x <= Tree[Tree[now].son[0]].size) now = Tree[now].son[0]; else int sz = 1; if (Tree[now].son[0]) sz += Tree[Tree[now].son[0]].size; if (x == sz) return now; x -= sz; now = Tree[now].son[1]; inline void erase(int x) int id = pos[x]; splay(id); if (!Tree[root].son[0] && !Tree[root].son[1]) Tree[root].size = Tree[root].value = 0; Tree[root].fa = 0; Tree[root].son[0] = Tree[root].son[1] = 0; root = 0; return; if (!Tree[root].son[0]) int tmp = root; root = Tree[root].son[1]; Tree[root].fa = 0; Tree[tmp].size = Tree[tmp].value = 0; Tree[tmp].son[0] = Tree[tmp].son[1] = 0; return; if (!Tree[root].son[1]) int tmp = root; root = Tree[root].son[0]; Tree[root].fa = 0; Tree[tmp].size = Tree[tmp].value = 0; Tree[tmp].son[0] = Tree[tmp].son[1] = 0; return; int now = Tree[root].son[0]; while (Tree[now].son[1]) now = Tree[now].son[1]; splay(now); Tree[now].son[1] = Tree[id].son[1]; Tree[Tree[id].son[1]].fa = now; Tree[id].fa = 0; pos[Tree[id].value] = 0; Tree[id].size = Tree[id].value = 0; Tree[id].son[0] = Tree[id].son[1] = 0; update(root); inline void insert_left(int x) Tree[root].son[0] = ++total; Tree[total].fa = root; Tree[total].son[0] = Tree[total].son[1] = 0; Tree[total].value = x; Tree[total].size = 1; pos[x] = total; update(root); inline void insert_right(int x) Tree[root].son[1] = ++total; Tree[total].fa = root; Tree[total].son[0] = Tree[total].son[1] = 0; Tree[total].value = x; Tree[total].size = 1; pos[x] = total; update(root); inline void Swap(int x,int y) int posx = pos[x]; splay(posx); int posy; if (y == -1) if (!Tree[posx].son[0]) return; posy = Tree[posx].son[0]; while (Tree[posy].son[1]) posy = Tree[posy].son[1]; else if (!Tree[posx].son[1]) return; posy = Tree[posx].son[1]; while (Tree[posy].son[0]) posy = Tree[posy].son[0]; swap(pos[Tree[posx].value],pos[Tree[posy].value]); swap(Tree[posx].value,Tree[posy].value); inline int ask(int x) splay(pos[x]); return Tree[Tree[root].son[0]].size; inline int query(int x) int ret = find(x); return Tree[ret].value; T; int main() scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++) scanf("%d",&a[i]); T.push_back(a[i]); for (int i = 1; i <= m; i++) char op[10]; int s,t; scanf("%s",op); if (op[0] == ‘T‘) scanf("%d",&s); if (n == 1) continue; T.erase(s); int x = T.find(1); T.splay(x); T.insert_left(s); if (op[0] == ‘B‘) scanf("%d",&s); if (n == 1) continue; T.erase(s); int x = T.find(n - 1); T.splay(x); T.insert_right(s); if (op[0] == ‘I‘) scanf("%d%d",&s,&t); if (t == 0) continue; T.Swap(s,t); if (op[0] == ‘A‘) scanf("%d",&s); printf("%d ",T.ask(s)); if (op[0] == ‘Q‘) scanf("%d",&s); printf("%d ",T.query(s)); 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 查看详情