Train Tracking

题目描述

每天早上，特快列车都会经过农场，驶向大城市；每天下午，它又会沿相反方向经过，返回郊区。今天，Bessie 打算在早上和下午都观察这趟列车。

Bessie 事先知道列车有 $N$ 节车厢（$1 \leq N \leq 10^6$），方便起见编号为 $0 \dots N-1$。第 $i$ 节车厢上写着一个 ID 数 $c_i$（$0 \le c_i \le 10^9$）。这些数字在早上和下午都能看见，因此对每节车厢 Bessie 有两次机会观察其数字。也就是说，列车早上经过时，Bessie 能依次观察到 $c_0$、$c_1$，一直到 $c_{N-1}$。下午列车经过时，她又能再次依次观察到 $c_0$、$c_1$，一直到 $c_{N-1}$。

Bessie 选定了一个整数 $K$（$1 \leq K \leq N$），她希望求出每个长度为 $K$ 的连续车厢区间中的最小 ID 数。她有一本笔记本可以用来计算，但笔记本很小，而她的字（蹄写？）又很大。例如，甚至可能没有足够空间写下全部 $N+1-K$ 个最小值。出于某些神秘原因，Bessie 在计算时愿意把最小值对着天空“哞”出来，因此至少输出本身不是问题。

列车马上就要到了！请帮助 Bessie 在列车经过两次的过程中求出这 $N + 1 - K$ 个最小值，并确保她能有效利用有限的笔记本空间。她的笔记本被分成 $5500$ 个区块，方便起见编号为 $0 \dots 5499$，每个区块恰好可以存储一个介于 $-2^{31}$ 到 $2^{31}-1$（含端点）的整数。初始时，每个区块都存储整数 $0$。

这是一道交互式题目，但你不会使用标准（或文件）I/O。具体来说，你必须实现如下函数，用来帮助 Bessie 有效管理她有限的笔记本空间： void helpBessie(int ID);

每当一节车厢经过（无论早上还是下午），你的函数都会被调用一次，其输入为该车厢上的 ID 数。你的 $\texttt{helpBessie}$ 实现可以调用以下函数： int get(int index) : 获取 Bessie 笔记本中给定下标处存储的整数值。 void set(int index, int value) : 将给定下标处的整数设置为给定值。 void shoutMinimum(int output) : 指示 Bessie 将给定的数字“哞”向天空。 int getTrainLength() : 返回 $N$，车厢数量。 int getWindowLength() : 返回 $K$，窗口长度。 int getCurrentCarIndex() : 返回当前正在经过的车厢编号。 int getCurrentPassIndex() : 若 Bessie 正在观察早上的经过则返回 $0$，若正在观察下午的经过则返回 $1$。

为了帮助你开始编写代码，我们提供了 C/C++ 和 Java 的初始模板。很遗憾，本题不支持 Python 和 Pascal 提交。

窗口最小值必须按顺序输出（因此区间 $0, 1, \dots, K-1$ 的最小值必须在区间 $1, 2, \dots, K$ 的最小值之前输出，依此类推），但除了这一顺序要求外，你的函数可以在任意一次调用中、任意时刻输出最小值。例如，你的函数可以在某些调用中不输出任何内容，也可以在其他调用中输出多个结果。

Bessie 的超短期记忆非常好，因此在 $\texttt{helpBessie}$ 函数内部的内存使用不受限制（除了正常的 256MB 限制）。然而，在两节车厢之间，Bessie 无法“记住”任何不在笔记本中的信息。因此，在两次函数调用之间，你的程序不得保留状态，除非通过 $\texttt{get}$ 和 $\texttt{set}$ 调用写入/读取笔记本。

输入格式

输出格式

10 3
5 7 9 2 0 1 7 4 3 6

5
2
0
0
0
1
3
3

提示

这意味着： 你不允许创建任何非常量的全局或静态变量。任何这样做的解法都会被取消资格。教练将手动检查提交，以验证解法符合本题精神。由于本题不需要文件 I/O，你也不允许在代码中进行任何文件 I/O。

你的程序在每个测试用例中进行的 $\texttt{set}$ 调用总数与 $\texttt{get}$ 调用总数之和，将被限制为 $25 \cdot 10^6$。

题目署名：Dhruv Rohatgi

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum