P4373 [USACO18OPEN] Train Tracking P
题目背景
鉴于本题存在特殊要求且大部分人**不遵守**，题解通道关闭。如确有正解，请联系管理员单独添加。
1. 你的程序不需要，也不应该包含 `grader.h` 头文件。
2. 请在程序中加入如下函数声明语句：
```cpp
int get(int);
void set(int,int);
void shoutMinimum(int);
int getTrainLength();
int getWindowLength();
int getCurrentCarIndex();
int getCurrentPassIndex();
```
题目描述
每天早晨特快列车会经过农场，开往大城市，每天下午它又会折回来，回到郊区。今天，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 有效管理她有限的笔记本空间：
```cpp
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 语言的程序。
```cpp
#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$ 次。
供题：Dhruv Rohatgi