# 区间最值

## 解法与署名

出题人解法：固定左端点，逐步扩展右端点，用两个堆维护区间有序后的两部分。Codex（GPT-6）整理实现、显式说明数量不变量并验证边界。程序：[std.cpp](std.cpp)。

另有并列的[滑动窗口方案](solution-alternative-sliding-window.zh.md)及[程序](alternative-sliding-window.cpp)：按长度直接输出，将空间从 $O(n^2)$ 降为 $O(n)$ ，时间阶相同，但需要支持删除的有序多重集。标程保留出题人算法，两种方案的时间与空间取舍均在此保留。

## 双堆不变量

较小部分包含 $\lfloor L/2\rfloor$ 个元素，较大部分包含 $\lceil L/2\rceil$ 个元素。 较小部分使用大根堆，较大部分使用小根堆。还要保证较小部分的每个元素都不大于较大部分的每个元素。重复值按出现次数存储。

先把新值放入较小堆。若较大堆还缺一个元素，就将较小堆的最大值移入较大堆。若此后较小堆最大值大于较大堆最小值，则交换这两个堆顶。

插入前两部分有序，只有新元素可能破坏边界，因此最多交换一次即可。同步维护较大堆的元素和：移入时加上该值，交换时加上移入值与移出值之差。

## 正确性

空区间开始时两个堆均为空。按上述插入与调整步骤，归纳得到每次扩展后，数量及边界有序不变量均成立。因此两堆恰好把区间排序后的元素按指定数量分开，从堆顶或已维护的和取得的答案就是较大一半的和。

对每个左端点从头建立两堆，右端点依次扩展，恰好枚举全部非空区间。结果先保存为长度与左端点的二维表，再按长度递增、左端点递增输出。

## 复杂度与数值

共 $n(n+1)/2$ 次扩展，每次常数次堆操作，总时间 $O(n^2\log(n+1))$ .堆需要 $O(n)$ 空间，保存答案需要 $O(n^2)$ 空间。输出本身需要 $\Omega(n^2)$ 时间。

令 $U=\max_i\lvert a_i\rvert$ .答案绝对值至多 $\lceil n/2\rceil U$ ，当前范围可达 $5\times10^{11}$ ，元素和必须使用 64 位整数。 负数不能舍弃；每个区间所选元素数量固定。

## 验证与运行

对三种小数值组成、长度不超过六的全部序列逐区间排序对拍，另测随机大数和负数。正式输入覆盖千元素的单调、全同与正负交替序列。

每题的 `tests/plan.json` 包含十份输入的固定种子和目的。编译程序后，可运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 只生成输入，`--case 01` 选择单份输入。独立验证脚本见 [check_r15.py](../../../tools/check_r15.py)。五轮交替计时与内存记录见[测量数据](../../../docs/benchmark-R15.json)，环境说明见[评测环境与性能](../../../docs/评测环境与性能.md)。有限测试与具体程序的计时不代替上面的证明，也不保证所有同阶实现都能在同一时限内通过。

## 实测结果

| 程序 | 最慢用例中位时间 | 峰值工作集 |
| --- | ---: | ---: |
| 标程 | 0.080116 秒 | 9.06 MiB |
| 补充程序 | 0.206423 秒 | 5.38 MiB |

参考时限为 0.5 秒。十份已测正式输入上，两份程序结果一致，均在该时限内完成。上述内存是包含进程开销的峰值工作集，时间与内存的最大值可能来自不同输入。