决策单调性

Kubic · 2022-04-11 10:09:55 · 个人记录

对于有决策单调性的问题，直接上分治可以做到 O(n\log n) 的优秀复杂度，这种方法非常好写，常数很小，并且很万能。

但是对于满足四边形不等式的矩阵，SMAWK 算法可以在 O(n) 的时间复杂度内求出每一行的最小值以及它的位置。

如果矩阵两维不一样大，那么复杂度就（可以这样认为）是 O(n+m)。

首先先探究满足四边形不等式的矩阵有什么性质。

令 pos_i 表示第 i 行最后一个最小值的位置。

四边形不等式：

\forall x,y,a_{x,y}+a_{x+1,y+1}\le a_{x,y+1}+a_{x+1,y}

推论：

\forall x_1<x_2,y_1<y_2,a_{x_1,y_1}\ge a_{x_1,y_2}\Rightarrow a_{x_2,y_1}\ge a_{x_2,y_2}

\forall x_1<x_2,y_1<y_2,a_{x_2,y_1}<a_{x_2,y_2}\Rightarrow a_{x_1,y_1}<a_{x_1,y_2}

pos_i\le pos_{i+1}

对于一个 n\times m 的矩阵，我们以 n,m 的大小关系分类讨论。

如果 n\ge m，那么把所有偶数行提出来归约到 \lfloor\dfrac{n}{2}\rfloor,m 规模的问题。然后对于每一个奇数行，在相邻两行的决策之间暴力枚举求答案，显然总枚举次数是 O(n+m) 的。
如果 n<m，则我们需要删去一些无用列使得 n=m。

现在重点来看 n<m 时如何删除所有无用列。

我们考虑求出一个下三角矩阵使得每一行的最小值都在其中。根据之前的性质可以发现一定存在这样的下三角矩阵。

假设当前考虑到第 i 列，已经加入了 k 列，z_j 表示第 j 个加入的列的编号：

如果 m-i+k+1=n，即剩下的列的个数不超过 n-k，那么就把这一列加入。
如果 a_{z_k,k}\ge a_{i,k}，那么此时第 z_k 列没有任何作用，删除第 z_k 列。
如果 a_{z_k,k}<a_{i,k}，那么此时第 i 列在前 k 行没有任何作用，可以得出：
- 如果 k<n，那么加入第 i 列。
- 如果 k=n，那么删除第 i 列。

这样做一次的时间复杂度是 O(m)。

当问题归约到 n=1 或 m=1 时，直接暴力完成。

毛估估一下，你就会拍案而起：这个算法时间复杂度显然是 O(n+m)！

板子题：CF1423M