区间最值¶

解法与署名¶

出题人解法：固定左端点，逐步扩展右端点，用两个堆维护区间有序后的两部分。Codex（GPT-6）整理实现、显式说明数量不变量并验证边界。程序：std.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 包含十份输入的固定种子和目的。编译程序后，可运行：

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

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

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

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