1. 问题重述

• 列车有 ( N ) 节车厢，每节车厢有一个 ID ( c_i )。
• Bessie 会看两次列车（早晨和下午），每次都是按顺序看到车厢 ( 0, 1, \dots, N-1 )。
• 要求对每个长度为 ( K ) 的连续车厢窗口，输出窗口内的最小 ID。
• 笔记本有 5500 个存储单元，编号 0~5499，每个单元可以存一个 int。
• 在两次调用 helpBessie 之间，除了笔记本上的内容，程序不能保留任何状态（不能有全局变量、静态变量等）。
• 可以调用：
  • get(index) 读笔记本
  • set(index, value) 写笔记本
  • shoutMinimum(value) 输出一个窗口最小值
  • 以及几个获取当前状态的函数。

2. 核心难点

• 不能保存状态，意味着必须利用笔记本在两次调用之间传递信息。
• 笔记本只有 5500 个单元，不能直接存下所有 ( N ) 个车厢 ID（( N ) 最大 ( 10^6 )）。
• 必须在两遍扫描（早晨 + 下午）中完成所有窗口最小值的计算。

3. 可行思路

这类问题通常的解法是 分块 + 单调队列。

3.1 第一遍（早晨）

目标：将数组分成大小为 ( B ) 的块，计算每个块的最小值及其位置。

• 用笔记本存储每个块的最小值和最小值的位置。
• 例如：
  • 单元 0 ~ 块数-1：存储块的最小值
  • 单元 B ~ B+块数-1：存储块最小值对应的原下标
• 这样，我们只需要大约 ( 2 \times \lceil N/B \rceil ) 个单元。

当第一遍结束时，我们知道了每个块的最小值。

3.2 第二遍（下午）

目标：计算每个窗口的最小值并输出。

3.2.1 单调队列维护当前窗口的最小值

• 在第二遍扫描时，维护一个单调递增双端队列（存下标）。
• 队列在笔记本中的存储方式：可以用一段固定区域循环存储（因为队列长度不会超过 ( K ) 太多）。
• 存储方式示例：
  • 笔记本一部分存队列的值（车厢 ID 通过 get 从第一遍存储中获取，或者直接存？不行，第二遍不能直接访问第一遍的 ID，除非第一遍已经存下来——但存所有 ID 需要 ( N ) 个单元，不够）。
  • 所以只能存下标，然后通过调用 getCurrentCarIndex() 和已知的第一遍存储的块信息来间接获取 ID。

3.2.2 利用块最小值加速

• 如果窗口完全包含若干个完整的块，并且知道这些块的最小值，就可以快速确定窗口最小值吗？
• 但窗口可能跨块，不能直接取块最小值，因为块的最小值位置可能不在窗口内。

实际上，USACO 官解的做法是：

1. 第一遍：计算每个块的最小值，并记录位置。
2. 第二遍：对于每个位置 ( i )，当它是某个窗口的结尾（即 ( i \ge K-1 )）时，计算该窗口的最小值。
   • 如果窗口完全落在一个块内，直接扫描窗口（但这样最坏 ( O(K) ) 可能太大？）
   • 如果窗口跨多个块，则最小值 = min(左边不完整块的最小值, 中间完整块的最小值, 右边不完整块的最小值)
   • 中间完整块的最小值已经在第一遍算出，但要注意最小值的位置必须在窗口内，所以不能直接用块最小值，除非块的最小值位置在窗口内。因此可能需要存储多个候选值。

3.3 实际可行方案（两遍单调队列）

更常见的实现：

第一遍：我们只记录每个块的最小值位置（因为 ID 可以在第二遍通过下标直接访问？不行，第二遍没有保存所有 ID，除非第一遍把 ID 存到笔记本——但这样需要 ( N ) 个单元，不够）。
所以第一遍不能直接存所有 ID，只能存块的最小值位置，第二遍再根据位置去获取 ID（但第二遍看不到第一遍的 ID，因为 ID 是作为参数传入的，第二遍时还是按相同顺序传入，所以我们可以用第一遍记录的位置在第二遍调用时获取对应的 ID，因为第二遍调用顺序和第一遍相同）。

因此可行方法：

• 第一遍：记录每个块的最小值位置（存到笔记本）。
• 第二遍：当再次扫描到该位置时，就知道该块的 ID 最小值。
• 第二遍用单调队列计算窗口最小值时，队列中存的是下标，值通过当前传入的 ID 参数得到（对完整块的最小值位置，当扫描到该位置时，它的 ID 就是块的最小值）。

3.4 笔记本空间分配

• 块的数量 ( \lceil N/B \rceil ) 约 1000（如果 ( B=1000 )，( N \le 10^6 )）。
• 存储块的最小值位置：1000 个单元。
• 存储单调队列（存下标）：最多 K 个，约 ( 10^6 ) 不行，但可以只存 ( O(B) ) 大小，因为我们可以按块处理。
• 实际上，我们可以将窗口最小值计算分成“块间”和“块内”两部分，用 RMQ 思想，但这里笔记本太小，不能做 ST 表。

4. 标准解法简述

USACO 官方解法（大致）：

1. 第一遍：

   • 将序列分块，块大小 ( B \approx 1000 )。
   • 对每个块，计算最小值，并记录最小值在块中的相对位置（或全局位置）。
   • 将这些信息存到笔记本中。

2. 第二遍：

   • 再次遍历序列，维护一个单调队列，但队列中不仅包含单个元素，还包含块的最小值（当块完全在窗口内时，用块的最小值代表该块）。
   • 当窗口移动时，更新队列：
     • 删除出窗的元素（或块）
     • 加入新进入窗口的元素（或块）
   • 输出队列前端的最小值。

关键点：在第二遍中，当遇到一个块的最小值位置时，可以将该块的最小值作为一个“代表”插入单调队列，从而减少队列长度。

5. 空间使用

• 块信息：( O(N/B) ) 个单元
• 单调队列：( O(N/B + B) ) 个单元
• 总空间约 2000~3000 个单元，小于 5500。

6. 总结

这道题的核心是：

• 利用分块减少存储量
• 第一遍预处理块最小值
• 第二遍利用单调队列合并块信息与单点信息，高效计算滑动窗口最小值
• 完全利用笔记本在两次调用间传递信息，不依赖全局变量

这样就能在两遍扫描、有限笔记本空间内解决 ( N ) 高达 ( 10^6 ) 的滑动窗口最小值问题。