2870 「USACO 2018 US Open Platinum」Train Tracking

题目译自 USACO 2018 US Open Contest, Platinum Problem 2. Train Tracking

每天早晨特快列车会经过农场，开往大城市，每天下午它又会折回来，回到郊区。今天，Bessie 会花时间观察它，早晨和下午都会。

Bessie 提前知道，列车有 $N$ 节车厢，方便起见，将其编号为 $0\sim N−1$。车厢 $i$ 有一个 ID $c_i$。在早晨和下午，所有的数字都是可见的，所以对于每节车厢 Bessie 有两次机会观察它的 ID。也就是说，当列车早晨经过的时候，Bessie 能够观察 $c_0$，然后是 $c_1$，直到 $c_{N−1}$。当列车下午驶回的时候，她又一次能够观察 $c_0$，然后是 $c_1$，直到 $c_{N−1}$。

Bessie 挑选了一个整数 $K$，她想要求出每个连续的 $K$ 节车厢中最小的 ID。她有一本能够帮助执行计算的笔记本，但是这个笔记本相当小，并且 Bessie 的手写（蹄写？）字相当大。比方说，可能没有足够的空间记下所有 $N+1-K$ 个最小值。由于某些神秘的原因，Bessie 满足于当她算出最小数的时候向天哞出这些数，所以这个问题至少还不成问题。

列车马上就要来了！帮助 Bessie 在列车经过两次之后求出这 $N+1−K$ 个最小数，确保她有效地利用她有限的笔记本空间。她的笔记本被分为 $5500$ 个部分，方便起见编号为 $0\sim 5499$，每个部分的空间恰好能够记录一个在 $[−2^{31} , 2^{31}−1]$ 之间的整数。最初的时候，每个部分都记录着整数 $0$。

请帮助 Bessie 有效管理她有限的笔记本空间。

这是一道交互式题目，你不需要使用标准（或文件）输入输出。具体地说，你需要实现下面的函数，这个函数用来帮助 Bessie 有效管理她有限的笔记本空间：

void helpBessie(int ID);

每当一节列车车厢经过的时候，无论是在早晨和下午，你的函数都会被调用，函数的输入是这节车厢的 ID。

你的 helpBessie 函数的实现可以调用下面这些函数：

• int get(int index)：获取记录在 Bessie 的笔记本上的给定的索引处的整数值（index）。
• void set (int index, int value)：设置给定的索引（index）处的值为给定的整数值（value）。
• void shoutMinimum (int output)：通知 Bessie 向天哞一个指定的数。
• int getTrainLength()：返回列车的车厢数 $N$。
• int getWindowLength()：返回窗口的长度 $K$。
• int getCurrentCarIndex()：返回当前正在通过的车厢编号。
• int getCurrentPassIndex()：如果 Bessie 正在观察早晨的列车返回 $0$，下午的列车返回 $1$。

为了帮助你开始编码，我们为你提供了初始的 C/C++ 模板。遗憾地，这道题目不支持 Python 和 Pascal 语言的程序。

#include "grader.h"

// If you find it necessary, you may import standard libraries here.

void helpBessie(int ID)
{
    // Put your code here.
}

调用 void shoutMinimum (int output) 函数进行输出。

各个窗口的最小数必须按顺序输出（所以车厢 $0,1,\cdots ,K−1$ 之中的最小值必须在车厢 $1,2,\cdots ,K$ 之中的最小值之前输出，等等），但是除了这个顺序的限制之外，你的函数可以在任何一次函数调用中任意多次地输出一些最小值。比如，你的函数可能在某几次调用中不产生任何输出，而在某几次调用中产生多个输出。

Bessie 拥有惊人的短时记忆能力，因此在 helpBessie 函数中没有任何的内存使用限制，除了要满足常规的 256MB 限制。然而，在车厢与车厢之间，Bessie 不能够「记住」任何不在笔记本中出现过的内容。所以在两次函数调用之间，你的程序除了通过 get 和 set 函数调用之外不能保存任何的状态。

这意味着：

不允许定义任何非常量的全局或静态变量。任何如此做的提交会被取消成绩。教练会人工检查所有的提交以验证是否符合题目要求。由于这个问题无需文件输入输出，所以也不允许在代码中使用任何的文件输入输出。

对于全部数据，$1\le N\le 10^6,0\le c_i\le 10^9,1\le K\le N$，你的程序进行的 set 调用和 get 调用的总次数被限制为 $25\times 10^6$ 次。

Problem credits: Dhruv Rohatgi