SMAWK 全单调矩阵搜索

削减列的关键是给每个弹出操作一份覆盖全部行的证据。按零起算位置编号，栈中第 $h$ 个列候选已经被证明不可能是前 $h$ 行的最左极小列：它入栈时，前一个更左的候选在比较行不差于它，全单调性的逆否命题把这种“不应选右列”传播到更上面的行。

现在若新列在第 $h$ 行严格击败栈顶旧列，全单调性又把胜负传播到下面所有行。旧列在上方已经失去资格，在当前及下方又被新列严格击败，于是整列可以安全删除。栈满时，新列在最后一行仍没有击败栈顶，那么在更上面的行也不能成为最左胜者，它同样可以丢弃。

每列至多入栈一次、弹栈一次，削减是线性的。但只削减到与行数一样多，还没有解出全部行。接着用分治公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。只求一半行；邻近已解行会给未解行夹出很窄的扫描区间。这两步交替，既减少候选，又减少问题高度。

一次完整的削减和返回 ​

取行坐标 $x=(0,2,3,5,6)$、列偏置 $b=(0,1,0,2,-1,1,0)$，令 $A_{i,j}=(x_i-j{)}^2+b_j$。平方距离加列常数保留 Monge 性，因而满足本算法前提。矩阵为

开始依次处理列 $0,1,2$。栈为 $[0,1]$ 时，新列 $2$ 在行 $1$ 的值为 $0$，优于旧列 $1$ 的 $2$，所以弹出 $1$；再与列 $0$ 比较行 $0$，新列值 $4$ 不优于 $0$，停止，得到 $[0,2]$。随后列 $4$ 在行 $2$ 击败列 $3$，最终保留列 $[0,2,4,5,6]$。

递归只处理行 $[1,3]$。这一层削减后保留列 $[2,4]$；再往下一层只处理行 $3$，选列 $4$。返回时行 $1$ 在列 $2,4$ 中选 $2$。

最后插值原表的偶数行：行 $0$ 只扫描列 $[0,2]$，选 $0$；行 $2$ 扫描 $[2,4]$，选 $4$；行 $4$ 扫描 $[4,5,6]$，选 $6$。答案是

这里方括号中的列列表指削减后保留的列，不是把它们之间所有原列重新加入。被淘汰的列已有不可能最优的证明，插值不必把它们找回来。

线性求值不等于每个小例子都更省 ​

示例实现未缓存重复查询，共调用接口 $36$ 次，而显式扫描整张 $5\times 7$ 表只需 $35$ 次。渐近线性界并不承诺每个小规模输入都减少常数，更不承诺接口缓存和递归开销免费。重要的是规模增大时不再必须访问二次数量的格子。

如果矩阵只是原表极小列非降，削列可能破坏正确性；如果取最左答案却在相等时弹旧列，会丢掉需要保留的最左极小列；如果表项求值本身需 $T$ 时间，求值部分成本要乘上 $T$。这三个问题分别属于数学前提、平局规则和成本模型。

削减只需 $O(|C|)$ 次比较。插值扫描区间按列顺序依次相接，内部不重叠，只有边界列可能被相邻区间共同访问，所以总成本为 $O(|R|+|S|)$。第一次削减后 $|S|\le |R|$，递归行数减半；后续各层的行数和保留列数形成几何级数，得到总时间、工作列表空间 $O(m+n)$。输出本身需要 $m$ 个列号。

在分段 DP 中，当前层各行对应终点 $j$，各列对应前一切点 $k$。上一层已经完整求出，且每个费用能由前缀和常数时间计算时，一次 SMAWK 就能解一层。若当前层表项还依赖尚未求出的当前层状态，不能直接把未知值包装成查询接口；需要额外的在线结构或不同算法。

非法候选的 $+\mathrm{\infty }$ 填充也必须保持全单调性。非负平方分段费用的下阶梯可行域有专门的证明；任意形状的缺项表不能靠补一个很大的常数就获得同样保证。把无穷写成有限哨兵时，还必须确保哨兵不会与真正费用混淆或在加法中溢出。