本文约定

$\left\vert S\right\vert$:集合$S$的元素数量

$\{x\vert p(x)\}$:符合$p(x)$的元素组成的集合

$\land$:逻辑与

$\lor$:逻辑或

前言

关于Pascal

Pascal已经离我们很远了，将要退出NOI的支持。实际上，现在OI已经很少用Pascal了，常规的都是C++。但是Pascal更容易学习和阅读，尽管标准提供的功能并不丰富。

关于Turbo Pascal

Turbo Pascal是我最早用的IDE，在Windows的时代，它已经相当古老了。现在虽然有Free Pascal，但是其稳定性和编译速度比不上TP。而GNU Pascal早已停止更新，虽然还能找到，但是相当难用。

TP的中文资料并不丰富，但是在bitsavers.org上有很多文档，在winworldpc可以获得各种版本的TP，这也成为了研究的基础。TP可以在CP/M-80,CP/M-86和DOS下使用，我只研究DOS的版本，毕竟CP/M更加古老。然而，在我用的win64平台上，根本不能运行16位的TP，所以我还需要PCem——一个PC模拟器。

本文以描述功能为主，并加上一些图片，避免涉及过多的代码。另外，本文第一版可以在[OLD]2017-04-09-Turbo-Pascal的历史.md中找到。

前言

有时我们需要出题，用什么好呢？

• MS Word?我从来不用，虽然是WYSIWYG¹
  • 细节格式调整复杂，结构不清晰
  • 商业格式，并且跨平台效果差
  • 数学公式不太美观和方便
  • 导出PDF不太完善
• Markdown?以前一直用，虽然方便快捷也有缺点(用Typora)
  • 表格支持差，不能合并单元格
  • 数学公式无法复制，显示为图片
  • 无法显式分页，写博客没问题，但是出题就不太好了
• $\LaTeX$!
  • 支持复杂的表格
  • 美观的数学公式
  • 结构清晰，能生成PDF书签

当然，缺点也很多：

• 安装、学习较为复杂
• 需要时间编译，Word和Typora都是WYSIWYG
• 中文需要一定的配置，虽然现在已经比较简单
• 写文章也需要debug……

前言

在算法竞赛中，I/O有时是影响效率的瓶颈。I/O优化可以被模板化，与具体问题无关，是常数优化的重要方式之一。看到网上有很多关于这方面的文章，我也想来自己研究一下。

NOI系列目前支持的语言有C，C++和Pascal，其中C++可以直接使用C的绝大多数功能（但也有例外），因此下面只考虑C++和Pascal两种语言。通常，每种语言都提供了几种平台无关的I/O方式，如C++中的scanf/printf，cin/cout，fread/fwrite，Pascal中的read/write，blockread/blockwrite。也有一些低级的平台有关的I/O方式，Windows和Linux(Unix)都提供了内存映射文件，效率更加高。

在算法竞赛中，I/O通常用文本文件，而数据只有整数、浮点数和字符串三种。把十进制的字符串转换成整数或浮点数需要一定的时间，而分离出字符串也需要一定的时间，这就是I/O优化的方向。我们通常优化了时间，但是也降低了通用性。

思路

这题也有很多方法，其实并不用可并堆。类似于上一种方法，计算出dfs序和每个点的深度，然后按深度降序排序。对于每个点，需要删除深度相差超过L的点，并加入当前点，在子树中统计答案。而这些用树状数组就可以了（单点修改+区间查询）。时间复杂度$O(N\log N)$

当然，还有一种更加巧妙的方法。用倍增求出$2^i$步祖先，然后就可以找到第一个距离超过L的祖先，用差分区间加，最后就能算出答案。时间复杂度也是$O(N\log N)$，下面提供了官方题解中的这种方法的代码供参考。

思路

应该可以发现，这题可以用贪心。有两个值需要满足比较麻烦，我们考虑对询问和牧草按照口感（绿色值）排序。这样，对于一个询问(Ai,Bi)，只要从口感大于等于Bi的牧草中选出价格最小的且大于等于Ai的牧草，这样可以证明是最优的。如果没有符合条件的牧草，就是无解。

用multiset来维护牧草的价格很方便，支持所有操作，当然价格可以重复。时间复杂度$O(N\log N)$