[BZOJ1861] [Zjoi2006]Book 书架

2024-01-09 12:48
文章标签 book zjoi2006 书架 bzoj1861

本文主要是介绍[BZOJ1861] [Zjoi2006]Book 书架,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1861

题目大意

支持操作
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本书的编号

constmaxn=100005;
varw:array[-1..maxn,1..5]of longint;x:array[-1..maxn]of longint;i,j,k:longint;n,m,a,b,sum,root:longint;cha,cha1:char;
procedure print(a:longint);
beginif w[a,1]<>-1 then print(w[a,1]);write(w[a,5],' ');if w[a,2]<>-1 then print(w[a,2]);if a=root then writeln;
end;procedure rotate(a,kind:longint);
var b,unkind:longint;
beginb:=w[a,3]; unkind:=kind xor 3;w[a,4]:=w[b,4]; dec(w[b,4],1+w[w[a,kind],4]);w[w[a,unkind],3]:=b; w[b,kind]:=w[a,unkind];w[a,unkind]:=b; w[a,3]:=w[b,3]; w[b,3]:=a;if w[a,3]<>-1thenif w[w[a,3],1]=bthen w[w[a,3],1]:=aelse w[w[a,3],2]:=a;
end;procedure splay(a,goal:longint);
var b,kind,unkind:longint;
beginwhile w[a,3]<>goal dobeginb:=w[a,3]; if w[b,1]=a then kind:=1 else kind:=2; unkind:=kind xor 3;if w[b,3]=goal then rotate(a,kind)elseif w[w[b,3],kind]=bthen begin rotate(b,kind); rotate(a,kind); endelse begin rotate(a,kind); rotate(a,unkind); end;end;if goal=-1 then root:=a;
end;procedure init(a:longint);
begininc(sum); x[a]:=sum;w[sum,1]:=-1; w[sum,2]:=-1; w[sum,3]:=root; w[sum,4]:=1; w[sum,5]:=a; w[root,2]:=sum; inc(w[root,4]);if a=n+1 then w[sum,5]:=-maxlongint;splay(sum,-1);
end;function getmax(a:longint):longint;
var tt:longint;
begintt:=a;while w[tt,2]<>-1 dott:=w[tt,2];exit(tt);
end;procedure top(a:longint);
var tt,fa:longint;
beginsplay(x[a],-1);splay(getmax(w[root,1]),root);w[w[root,1],2]:=w[root,2]; root:=w[root,1]; w[w[root,2],3]:=root; w[root,3]:=-1; w[root,4]:=w[w[root,1],4]+1+w[w[root,2],4];splay(x[0],-1);tt:=w[root,2]; inc(w[root,4]);while tt<>-1 dobegin inc(w[tt,4]); fa:=tt; tt:=w[tt,1]; end;w[x[a],1]:=-1; w[x[a],2]:=-1; w[x[a],3]:=fa; w[x[a],4]:=1; w[x[a],5]:=a; w[fa,1]:=x[a]; splay(x[a],-1);
end;procedure bottom(a:longint);
var tt,fa:longint;
beginsplay(x[a],-1);splay(getmax(w[root,1]),root);w[w[root,1],2]:=w[root,2]; root:=w[root,1]; w[w[root,2],3]:=root; w[root,3]:=-1; w[root,4]:=w[w[root,1],4]+1+w[w[root,2],4];splay(x[n+1],-1);tt:=w[root,1]; inc(w[root,4]);while tt<>-1 dobegin inc(w[tt,4]); fa:=tt; tt:=w[tt,2]; end;w[x[a],1]:=-1; w[x[a],2]:=-1; w[x[a],3]:=fa; w[x[a],4]:=1; w[x[a],5]:=a; w[fa,2]:=x[a]; splay(x[a],-1);
end;procedure ask(a:longint);
beginsplay(x[a],-1);writeln(w[w[root,1],4]-1);
end;procedure query(a:longint);
var tt:longint;
begininc(a); tt:=root;while (w[w[tt,1],4]>=a)or(a>=w[w[tt,1],4]+2) doif a<=w[w[tt,1],4]then tt:=w[tt,1]else begin dec(a,w[w[tt,1],4]+1); tt:=w[tt,2]; end;writeln(w[tt,5]);
end;procedure insert(a,b:longint);
var tt,fa,c:longint;
beginif b=0 then exit;splay(x[a],-1); c:=w[w[root,1],4]+b+1;splay(getmax(w[root,1]),root);w[w[root,1],2]:=w[root,2]; root:=w[root,1]; w[w[root,2],3]:=root; w[root,3]:=-1; w[root,4]:=w[w[root,1],4]+1+w[w[root,2],4];tt:=root;while (w[w[tt,1],4]>=c-1)or(c-1>=w[w[tt,1],4]+2) doif c-1<=w[w[tt,1],4]then tt:=w[tt,1]else begin dec(c,w[w[tt,1],4]+1); tt:=w[tt,2]; end;splay(tt,-1);tt:=w[root,2]; inc(w[root,4]);while tt<>-1 dobegin inc(w[tt,4]); fa:=tt; tt:=w[tt,1]; end;w[x[a],1]:=-1; w[x[a],2]:=-1; w[x[a],3]:=fa; w[x[a],4]:=1; w[x[a],5]:=a; w[fa,1]:=x[a];
end;beginreadln(n,m); sum:=1; root:=1;w[1,1]:=-1; w[1,2]:=-1; w[1,3]:=-1; w[1,4]:=1; w[1,5]:=-maxlongint; x[0]:=1;for i:=1 to n dobegin read(a); init(a); end;init(n+1);readln;//print(root);for i:=1 to m dobeginread(cha);if (cha='B')or(cha='I')then for j:=1 to 5 do read(cha1)elseif (cha='Q')then for j:=1 to 4 do read(cha1)else for j:=1 to 2 do read(cha1);case cha of'T':begin readln(a); top(a); end;'B':begin readln(a); bottom(a); end;'I':begin readln(a,b); insert(a,b); end;'A':begin readln(a); ask(a); end;'Q':begin readln(a); query(a); end;end;//print(root);end;
end.

这篇关于[BZOJ1861] [Zjoi2006]Book 书架的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/587164

相关文章

【SGU】271. Book Pile(双端队列模拟)

一摞书,2个操作,一个操作是在书堆上加一本,第二个将前K个书翻转 看别人用Splay树做的,但是可以用双端队列模拟,因为K个书之后的书位置已经定下来了,所以只需要记录在队列头加书还是尾加书 #include<cstdio>#include<string>#include<algorithm>#include<queue>#include<stack>#include<cstrin

Mac book 系统清理

重置 PRAM/NVRAM command+option  + P + R 您的电脑中很小的一部分内存,被称为“参数随机存取存储器”或 PRAM,它将某些设置储存在 Mac OS X 可以快速访问的位置。储存的特定设置取决于您的 Mac 类型以及连接在 Mac 上的设备的类型。这些设置包括您指定的启动磁盘、显示器分辨率、扬声器音量和其他信息。 详细步骤: 关闭电脑。在键盘上找到以下键:Co

基于HTML5 Canvas的CSG构造实体几何书架

CSG 构造实体几何这个概念在工业水利水电施工上、游戏上已经有很多人使用了,最简单的实体表示叫作体元,通常是形状简单的物体,如立方体、圆柱体、棱柱、棱锥、球体、圆锥等。根据每个软件包的不同这些体元也有所不同,在一些软件包中可以使用弯曲的物体进行 CSG 处理,在另外一些软件包中则不支持这些功能。构造物体就是将体元根据集合论的布尔逻辑组合在一起,这些运算包括:并集、交集以及补集。我们一般可以用 C

企业网络解决方案资料书架

企业网络解决方案资料书架 https://info.support.huawei.com/info-finder/vue/#/zh/enterprise/bookshelf/horizontalsolution/cloudcampushttps://support.huawei.com/enterprise/zh/doc/EDOC1100368563/d25f7f44

大语言模型 LLM book 笔记(三)第五章 模型架构

第五章 模型架构 5.1 Transformer 模型 5.1.1 输入编码 词元序列变成固定维度的词向量,加上固定维度的绝对位置编码 5.1.2 多头自注意力机制(Multi-head Self-attention) 单头:对于输入的词元序列,将其映射为相应的**查询(Query, 𝑸)、键(Key, 𝑲)和值(Value, 𝑽)**三个矩阵,然后,对于每个查询,将和所有没有被掩

【ATU Book-i.MX8系列 - TFLite 进阶】 NXP i.MX8M Plus 实现高效 Mobilenet SSD 物体检测

NXP i.MX8M Plus 实现高效 Mobilenet SSD 物体检测 一、概述 在 边缘运算(Edge Computing) 领域中,轻量级的模型扮演着举足轻重的角色。因此,如何在有限硬体资源下实现电脑视觉(Computer vision) 应用是个极具挑战性的课题。特别是在效能与准确度之间寻求平衡。在本节中,我们将深入剖析 深度学习(Deep Learning) 领域中一个备受关注

[linux-005]一个xelatex的book模板

% xelatex book 模板,编译命令:xelatex cjmst.tex,结果是pdf文件。\documentclass[openright,twoside, a4paper, 12pt]{book}\usepackage[UTF8]{ctex}\usepackage{fancyhdr}\pagestyle{fancy}\begin{document}% 书名和作者信息\titl

android书架,可以拖动的图书

需要实现这样的功能:         1)书架的风格可以切换;         2)书籍在整个书架上可以随意拖动,书架可以上下滚动;         3)书籍只能放在书架层上;         4)点击书籍可以动画放大书籍; 依次来解决问题,1)书架的风格可以切换,可以定义几个xml界面

The book

Deep Learning for Coders with Fastai and PyTorch: AI Applications Without a PhD is the book that forms the basis for this course. We recommend reading the book as you complete the course. There’s