# 区间中位数

## 解法与署名

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

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

## 双堆不变量

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

插入新元素时，若较小堆为空或新值不大于其堆顶，放入较小堆，否则放入较大堆。若较小堆数量不符，从相应堆顶移动一个元素修正。插入和移动都保持两部分有序。

奇数长度时答案为较小堆顶的二倍；偶数长度时答案为两个堆顶之和。比较容器大小时用有符号整数或加法形式，避免无符号减法下溢。

## 正确性

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

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

## 复杂度与数值

共 $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$ .答案绝对值至多 $2U$ .虽然当前范围内能放入有符号 32 位整数，程序统一使用 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.074143 秒 | 9.11 MiB |
| 补充程序 | 0.206148 秒 | 5.38 MiB |

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