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 了。