YZOJ P2319 宇宙图书馆

YZOJ P2319 宇宙图书馆

时间限制:1000MS      内存限制:131072KB

难度: \(3.4\)

  • 题目描述

宇宙图书馆(Universal Library)是一个规模巨大的图书馆,该图书馆收集各个星球出版的大量系列图书。为了统一时间,宇宙图书馆的每本书的出版年份以 “宇宙年” 为单位来记录。当然,尽管图书馆可以存非常多的书,但书不能无休止地增加,因此管理员会定期剔除出版年份小于某个数的所有书。

由于书的数量多,无法手工统计,你需要编写一个图书管理系统,来管理宇宙图书馆的图书记录。

  • 输入格式

第一行为一个正整数 \(N\),为该系统设定的出版年份上限(单位:宇宙年,之后涉及的所有出版年份均为 \(1\) 到 \(N\) 之间的正整数。

之后,每行一个合法的命令,命令有以下五种:

Add t x:添加一套共 \(x\) 本书(\(x\) 为正整数),这一套书的出版年份均为 \(t\)(单位:宇宙年);

Remove t:删除所有出版年份小于 \(t\) (单位:宇宙年)的书,并输出被删除的书的数量;

Count a b:统计出版年份(单位:宇宙年)在 \(a, b\) 之间(含 \(a, b\),保证 \(a \leq b\) )的书的数量,并输出;

List x:将所有书按出版年份从大到小(也就是从新到旧)顺序列出,但由于输出可能较多,这里只要求输出列表中给定的第 \(x\) 本书的出版年份(如果不存在,输出 No);

Quit:退出系统,结束程序。

  • 输出格式

对每个 Remove、Count、List 命令,输出一行答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

水题,详细的范围就不贴了

保证 \(1 \leq N, \) 总操作次数 \( \leq 100,000\) ,计算过程中出现的数保证不超过 \(10^9\) 。

 

 

 


 

 

 

线段树裸题?

没错就是线段树裸题,不知道为什么我考场上写了个 \(O(Nlog^2N)\) 的。。。。

把年份拿去开一棵线段树,Add 就是单点修改,Remove 就是区间修改,Count 就是区间查询,就是这个 List 有点东西。

考虑一下怎么求线段树中第 \(k\) 本书的位置。

首先考虑这样一个线段树,F 为父节点,Ls、Rs 分别为左右子节点。

因为是线段树,所以考虑递归查找对于父节点来说第 \(k\) 本书的位置。

很显然有下面两种情况:

如果左子节点中,书的数量不比 \(k\) 小,那么第 \(k\) 本书一定在左子节点中,并且对于左子节点来说要查找的也是第 \(k\) 本书。

如果左子节点中,书的数量比 \(k\) 小,那么第 \(k\) 本书一定在右子节点中,但是对于右子节点来说要查找的就变为第 \(k – sum_{Ls}\) 本书了(\(sum_{Ls}\) 表示左子节点书的数量)。

要是 \(k\) 比当前所有书总量还多,那就是 No 了。

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注