关键词:
[ZJOI2006]书架
题目描述
小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。
小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引力了,所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的,所以每次放书的时候至少能够将那本书放在拿出来时的位置附近,比如说她拿的时候这本书上面有X本书,那么放回去时这本书上面就只可能有X-1、X或X+1本书。
当然也有特殊情况,比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面,然后转身离开。
久而久之,小T的书柜里的书的顺序就会越来越乱,找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序,处理她看书时的一些操作,以及回答她的两个提问:(1)编号为X的书在书柜的什么位置;(2)从上到下第i本书的编号是多少。
输入输出格式
输入格式:
第一行有两个数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本书的编号。
输出格式:
对于每一条Ask或Query语句你应该输出一行,一个数,代表询问的答案。
输入输出样例
输入样例#1:
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:
2
9
9
7
5
3
说明
100%的数据,(n,m <= 80000)
Solution
bzoj1861
对于书的顺序,我们可以认为这些书有一个优先级,优先级越小代表它在书架中的顺序越靠前,所以对于这些操作,其实就是要我们维护一个优先级
k小值??? 平衡树!!!
本蒟蒻只会splay和(set/vector,,模拟平衡树),所以在这里摆上splay的做法
在这道题中,splay维护的不再是中序遍历的结果,而是一个优先级
- Top s ( o)找到s在splay的编号,删除后,将其优先级调道最小重新插入
- Bottom s ( o)和上面一样,将优先级调到最大再插入
- Insert s,t ( o)将s和其前驱/后继交换位置,实质是都删除,交换优先级,再重新插入,比直接交换所有信息快的多
- Ask s ( o)查询s的排名
- Query s ( o)查询第s小值
那么实际上如何操作呢?我们在读入的时候,给每本书的编号x加一个id[x]=i,splay维护的就是这个id[]
那么在插入的时候,我们就不能像之前那样直接插入一个权值,而是要先找到它的优先级在splay中对应的节点在哪?再插入
void insert(int rank,int v)
int u=root,f=0;
while(u && t[u].rk!=rank)
f=u;
u=t[u].ch[rank>t[u].rk];
u=++tot;
if(f) t[f].ch[rank>t[f].rk]=u;
t[u].size=1; t[u].rk=rank;
t[u].ch[0]=t[u].ch[1]=0;
t[u].val=v,t[u].f=f;
splay(u,0);
Insert操作如果懂了怎么实现的话应该不用摆代码了
Ask/Query是平衡树基本操作
那么直接上代码了
提示:因为我们会不断的删除节点,而又没有回收它的编号,所以在insert函数中,编号是一直在变大的,数组稍微开大点
Code
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int N=2e5+10;
const int inf=2e9;
void in(int &ans)
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') if(i=='-') f=-1; i=getchar();
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
ans*=f;
int n,root,tot,m;
int minx,maxn;
int rk[N],id[N];
struct Splay
int f,size,ch[2],val,rk;
t[N];
il bool get(int x)
return t[t[x].f].ch[1]==x;
il void up(int x)
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
void rorate(int x)
int f=t[x].f,gf=t[f].f;
int k1=get(x),k2=get(f);
t[f].ch[k1]=t[x].ch[k1^1], t[t[x].ch[k1^1]].f=f;
t[gf].ch[k2]=x, t[x].f=gf;
t[f].f=x, t[x].ch[k1^1]=f;
up(f); up(x);
void splay(int x,int goal)
while(t[x].f!=goal)
int f=t[x].f,gf=t[f].f;
if(gf!=goal)
(get(x)^get(f))?rorate(x):rorate(f);
rorate(x);
if(!goal) root=x;
void insert(int rank,int v)
int u=root,f=0;
while(u && t[u].rk!=rank)
f=u;
u=t[u].ch[rank>t[u].rk];
u=++tot;
if(f) t[f].ch[rank>t[f].rk]=u;
t[u].size=1; t[u].rk=rank;
t[u].ch[0]=t[u].ch[1]=0;
t[u].val=v,t[u].f=f;
splay(u,0);
void find(int rank)
int u=root; if(!u) return;
while(t[u].ch[rank>t[u].rk] && rank!=t[u].rk)
u=t[u].ch[rank>t[u].rk];
splay(u,0);
int kth(int k)
int u=root; if(t[u].size<k) return 0;
while(1)
int y=t[u].ch[0];
if(k>t[y].size+1)
k-=t[y].size+1;
u=t[u].ch[1];
else if(k<=t[y].size) u=y;
else return t[u].val;
int Rank(int x)
find(x); int u=root;
return t[t[u].ch[0]].size+1;
int Get(int rank,int f)
find(rank); int u=root;
if(t[u].rk>rank && f) return u;
if(t[u].rk<rank && !f) return u;
u=t[u].ch[f];
while(t[u].ch[f^1]) u=t[u].ch[f^1];
return u;
void Del(int x)
int last=Get(x,0),nex=Get(x,1);
splay(last,0); splay(nex,last);
t[nex].ch[0]=0;
void work(int x,int f)
find(id[x]);
int v=t[root].val; Del(id[x]);
if(!f) id[x]=--minx,insert(id[x]=--minx,v);
else insert(id[x]=++maxn,v);
void sp(int x,int f)
if(!f) return;
int rk1=Rank(id[x]),rk2=rk1+f;
int v1=x,v2=kth(rk2);
Del(id[v1]); Del(id[v2]);
swap(id[v1],id[v2]);
insert(id[v1],v1); insert(id[v2],v2);
il void Ask(int x)
find(id[x]); int u=root;
printf("%d
",t[t[u].ch[0]].size-1);
il void Query(int x)
printf("%d
",kth(x+1));
int main()
in(n); in(m);
minx=1,maxn=n; int x,y;
insert(inf,inf); insert(-inf,-inf);
for(int i=1;i<=n;i++) in(x),insert(id[x]=i,x);
for(int i=1;i<=m;i++)
char s[10]; scanf("%s",s);
if(s[0]=='T') in(x),work(x,0);
if(s[0]=='B') in(x),work(x,1);
if(s[0]=='I') in(x),in(y),sp(x,y);
if(s[0]=='A') in(x),Ask(x);
if(s[0]=='Q') in(x),Query(x);
return 0;
博主蒟蒻,随意转载.但必须附上原文链接
http://www.cnblogs.com/real-l/
解题: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 查看详情