# 简单合并：胜者树

Codex（GPT-6）将已有的胜者树方法应用于本题的多路归并。程序：[alternative-tournament.cpp](alternative-tournament.cpp)。堆解法与共同建模见[主解](solution.zh.md)。

## 固定叶子的选拔

把每个单调序列转为不降顺序。建立一棵完全二叉树，每个实际叶子保存一个序列的当前首元素和编号。叶子数补至不小于 $k$ 的最小二次幂，补充叶子以及已空序列使用无穷大哨兵。

每个内部结点保存两个孩子中较小的条目。根结点便是全部序列首元素中的最小值。每次输出根结点的值，推进获胜序列的指针，更新对应叶子，再向根逐层重新取最小值。

## 正确性

叶子正确表示各序列当前的候选值。按树高归纳，每个内部结点保存其子树全部叶子的最小值，因此根是全局最小首元素。更新一个叶子只会影响它到根的祖先链，逐层重算即可恢复该性质。结合主解的首元素论证，输出符合全部操作。

## 复杂度与适用条件

设 $S=\sum s_i$ .初始化与读入为 $O(S+k)$ ，每次操作为 $O(\log(k+1))$ ，总空间 $O(S+k)$ .当 $k=1$ 时根本身就是叶子，更新循环自然为空。

胜者树每次只替换一个固定叶子，逻辑规整；堆可以直接使用标准库。二者都是完整范围的有效算法。哨兵使用大于合法输入的 64 位数；不允许把合法的最大输入值当作空序列。实测适用性见[主解](solution.zh.md#验证与运行)。