很多分治代码的递归部分只有三四行，真正决定正确性和复杂度的是 Combine。合并不是固定的“双指针模板”，它可能是有序归并、跨区间统计、结构拼装、性质保持，也可能是两个结果集合的笛卡尔积。
模式一：合并两个有序区间
12E08 · Sort an Array的子调用返回后，两半分别有序。合并时维护：
PROP不变量 · 归并前缀
临时数组已经写入的前缀，恰好包含两个输入区间已处理元素的全部值，并按非递减顺序排列；两个指针分别指向各自区间尚未处理的最小值。
每一步选择两个指针中的较小者，便不会漏掉更小元素。某一半耗尽后，另一半剩余元素已经有序，可以直接复制。
while (i < middle || j < right) {
if (j == right || (i < middle && a[i] <= a[j])) {
buffer[write++] = a[i++];
} else {
buffer[write++] = a[j++];
}
}相等时先取左侧可以保留稳定性。若题目只要求数值排序，稳定性未必影响答案，但明确规则让实现更容易推理。
模式二：借助有序性批量计数
逆序对
12E11 · 逆序对中，两半内部答案已经递归统计。合并时若 right[j] < left[i]，由于左半有序，从 i 到末尾的所有元素都大于 right[j]，一次增加 middle-i。
这比逐对比较快的原因是：有序性把一批相同结论压成一次计数。
WARN易错点 · 等号改变题意
逆序对条件是严格大于。若合并比较使用 left[i] < right[j]，相等时会先取右侧并误把相等元素计入逆序对。应在 left[i] <= right[j] 时先取左侧。
重要翻转对
12E14 · Reverse Pairs的条件变成 left[i] > 2*right[j]。它不再与普通归并取元素的时刻完全一致，因此分成两步：
- 两半有序后，用单调右指针统计跨区间答案；
- 再执行普通归并，为上层建立有序性。
右指针无需为每个 i 回退，因为左值递增时，满足条件的右侧前缀只会扩大。
逐元素答案
12E15 · Count of Smaller Numbers After Self不能只返回总数。合并的对象应改为原下标；当取出一个左半元素时，已经先取出的右半元素都严格更小，于是把这个数量加到该原下标的答案。
IDEA直觉 · 合并什么，取决于答案需要什么
只求总数时可以累加一个标量；需要每个位置的答案时，必须携带原下标；需要恢复树时，子结果必须是结点。Combine 的输出类型来自题目最终输出，不来自模板。
范围计数
12E16 · Count of Range Sum对每个左前缀和 x，需要统计右半中满足
的 y。在有序右半上维护两个不回退的指针：第一个指向首个 y-x≥lower，第二个指向首个 y-x>upper，两者之差就是当前贡献。
模式三：中心接口制造独立子问题
12E10 · 地毯填补的棋盘只有一个真实洞。四分后，只有一个象限天然含洞，另外三个象限还不满足子问题合同。
Combine 的关键动作发生在递归之前：在棋盘中心放一块 L 形骨牌，分别占据另外三个象限的中心角，于是每个象限都恰好有一个洞，四个子问题终于同构。
EX示例 · “先补接口，再递归”
设真实洞位于左上象限。中心骨牌覆盖右上、左下、右下象限靠中心的一个格子，这三个覆盖格在各自子问题中被当作虚拟洞。随后四象限可以独立递归。
这与归并排序“先递归再合并”的时间顺序不同，却仍属于分治：关键是建立子问题合同并组合覆盖，不是代码必须按某个固定排列出现。
模式四：结构拼装
12E09 · Construct Quad Tree的 Combine 创建一个内部结点，并按左上、右上、左下、右下连接四棵子树。
结构题常有多种等价序列化。为了自动评分，本地合同固定：
- 内部结点 token 为
I； - 叶子为
L0或L1； - 使用前序遍历；
- 四个孩子顺序固定。
算法正确和输出可复现是两个维度。树可能构造正确，但序列化顺序不一致仍不符合本 Lab 的标准输入输出合同。
模式五：结果集合的笛卡尔积
12E12 · Different Ways to Add Parentheses枚举一个运算符作为最后执行的操作。左子表达式可能有多个结果，右子表达式也可能有多个，当前运算符必须组合每一对左右结果。
若左侧有
ANTI反例 · 用 set “优化”重复结果
题目要求保留每种括号化方式产生的结果。两个不同括号结构可能得到同一个数值；用 set 去重会改变输出重数，因而改变问题定义。
模式六：用变换保持性质
12E13 · Beautiful Array利用一个性质：若数组中不存在三项等差结构，对所有元素执行同一个正仿射变换后仍保持该性质。
递归得到较小漂亮数组后：
- 映射
2x-1得到全部奇数； - 映射
2x得到全部偶数； - 奇偶两组之间不可能以某个整数作为平均数形成违规三元组。
本地固定奇数组在前、偶数组在后，解决“合法答案不唯一”带来的测试不确定性。
选择 Combine 的检查表
| 问题信号 | 常见合并方式 |
|---|---|
| 两半各自有序 | 双指针归并 |
| 统计跨区间数对 | 单调指针、前缀数量或归并时批量计数 |
| 输出逐元素答案 | 携带原下标并把贡献写回 |
| 构造树/图形 | 建父结点、偏移坐标、固定子结果顺序 |
| 枚举所有结果 | 子结果集合笛卡尔积 |
| 构造满足全局性质的对象 | 找到保持性质的映射或连接规则 |
自检
- 为什么统计跨区间关系前常要求两半有序？
- 地毯填补的中心骨牌为什么不是普通意义上的“递归后合并”？
- 多解构造题为什么应在本地 Lab 中规定规范输出？
参考答案
- 有序性让“某个元素满足条件”扩展为连续前缀或后缀，从而用指针差一次统计一批，而不是逐对检查。
- 它先把三个不满足“恰有一个洞”的象限改造成合法子问题，再递归；合并体现为中心骨牌与四个子覆盖共同构成完整覆盖，不要求时间顺序一定在子调用之后。
- 自动判题需要唯一可比较的 oracle。规定遍历或构造顺序不会否认其他答案正确，但明确了课程环境实际接受的子集。
下一节将把这些不变量组织成终止性与正确性证明。