简单合并¶

解法与署名¶

出题人解法：各序列统一为不降顺序，用堆维护每个未空序列的首元素。Codex（GPT-6）整理标准 C++17 实现与重复值、零次操作的边界。程序：std.cpp。

另提供胜者树与程序，用固定叶子和逐层取最小值维护同一个候选集合。两者同阶；堆仍为首选，胜者树提供不同的更新结构，不把同阶替代称为渐进优化。

设总元素数为 \(S=\sum s_i\) .若一个序列首元素大于末元素，将其翻转；否则它已经不降，首尾相等时由单调性可知整个序列相等。

每个未空序列的最小剩余元素位于当前首位置。因此所有剩余元素的最小值，一定在这些首元素中。

把每个首元素及其所属序列编号放入最小堆。每次弹出堆顶并输出，只向前移动这个序列的指针；它仍非空时，把新的首元素加入堆。

初始堆恰好包含每个未空序列的首元素。假设操作前保持该不变量，堆顶就是全局最小值。删除它只改变一个序列的首元素，补入这个序列的新首元素便恢复不变量。由操作次数归纳，全部输出正确。

重复值按出现次数分别保留。序列编号只用于相等值之间稳定比较，不改变输出的数值。\(m=0\) 时完成读入后不弹堆；\(m=S\) 时恰好删光全部元素。

读入和翻转共 \(O(S)\) .当前程序逐个插入初始首元素，堆操作共 \(O((k+m)\log(k+1))\) ，总时间 \(O(S+(k+m)\log(k+1))\) .存储全部输入和堆需要 \(O(S+k)\) 空间。

胜者树初始化为 \(O(k)\) ，每次替换一个叶子为 \(O(\log(k+1))\) ，总时间 \(O(S+k+m\log(k+1))\) ，空间同为 \(O(S+k)\) .由于 \(k\le S\) ，两者总时间阶相同；具体耗时以实测为准。

用展平全部元素后排序的独立模型对拍，覆盖不同单调方向、重复值、零次删除及删光全部元素。

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

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

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

程序	最慢用例中位时间	峰值工作集
标程	0.176663 秒	9.00 MiB
补充程序	0.159656 秒	9.01 MiB

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