零、前置知识
-
子矩阵：
设 \(A\) 为 \(n\times m\) 的矩阵，则子矩阵 \(A_{[i_1,\cdots,i_k],[j_1,\cdots,j_l]}\) 为矩阵 \(A\) 的第 \(i_1,\cdots,i_k\) 行与第 \(j_1,\cdots,j_l\) 列的交形成的矩阵。
-
连续子矩阵：
连续子矩阵 \(A_{[i_1\sim i_2],[j_1\sim j_2]}=A_{[i_1,i_1+1,\cdots,i_2],[j_1,j_1+1,\cdots,j_2]}\)。
-
行最小值位置：
定义 \(\min_{i}(A)\) 为最大的整数 \(k\) 满足 \(\forall 1 \leq j \leq n,A_{i,j} \geq A_{i,k}\)。
-
单调矩阵：
对于 \(n\times m\) 的矩阵 \(A\)，若 \(\forall 1 \leq i < j \leq n,\min_{i}(A) \leq \min_{j}(A)\)，则称该矩阵为单调矩阵。
-
完全单调矩阵：
对于 \(n\times m\) 的矩阵 \(A\)，若其所有子矩阵均为单调矩阵，则称该矩阵为完全单调矩阵。
-
四边形不等式与蒙日阵
对于 \(n\times m\) 的矩阵 \(A\)，若对于任意 \(1 \leq i_1 \leq i_2 \leq n,1 \leq j_1 \leq j_2 \leq m\)，均有 \(A_{i_1,j_1}+A_{i_2,j_2} \leq A_{i_1,j_2}+A_{i_2,j_1}\)，则称 \(A\) 满足四边形不等式，同时称 \(A\) 为蒙日阵。
-
定理 0.1：矩阵 \(A\) 满足四边形不等式当且仅当 \(\forall 1 \leq i < n,1 \leq j < m,A_{i,j}+A_{i+1,j+1} \leq A_{i,j+1}+A_{i+1,j}\) 。
证明：必要性显然。将 \(A_{i,j}+A_{i+1,j+1} \leq A_{i,j+1}+A_{i+1,j}\) 和 \(A_{i+1,j}+A_{i+2,j+1} \leq A_{i+1,j+1}+A_{i+2,j}\) 相加，即可得到 \(A_{i,j}+A_{i+2,j+1} \leq A_{i,j+1}+A_{i+2,j}\)，可以无限向右扩展。向下扩展同理，可以证明其充分性。
-
定理 0.2：若矩阵 \(A\) 满足四边形不等式，则 \(A\) 与 \(A^T\) 均为完全单调矩阵。
证明：设 \(A\) 的子矩阵 \(A'\) 不是单调矩阵，则存在 \(\min_{i}(A') > \min_{i+1}(A')\)，此时 \(A'_{i,\min_{i+1}(A')}+A'_{i+1,\min_{i}(A')} > A'_{i,\min_{i}(A')}+A'_{i+1,\min_{i+1}(A')}\)，与四边形不等式矛盾。\(A^T\) 同理。
更多有关蒙日矩阵的性质会在第四章节进行讲述。
考虑以下两种形式的动态规划（忽略初始值）：
- \(f_{i,j}=\min\limits_{1 \leq k < j}{f_{i-1,k}+w_{k,j}}\)
此时从 \(f_{i-1}\) 转移到 \(f_{i}\) 时可以构造如下 \(n \times n\) 的矩阵 \(A\)：
那么 \(f_{i,x}=A_{x,\min_{x}(A)}\)，在矩阵 \(A\) 满足四边形不等式时可以快速计算。由于转移时 \(f_{i-1}\) 已知，我们不妨将其称为离线决策单调性。
-
定理 0.3：在上述离线决策单调性问题中，若 \(w\) 满足四边形不等式，则 \(A\) 也满足四边形不等式。
证明：只需证明对于所有 \(i_1 \leq i_2,j_1 \leq j_2\)，都有 \(A_{i_1,j_1}+A_{i_2,j_2} \leq A_{i_1,j_2}+A_{i_2,j_1}\)。
\[\begin{aligned} A_{i_1,j_1}+A_{i_2,j_2} & =f_{i-1,j_1}+w_{j_1,i_1}+f_{i-1,j_2}+w_{j_2,i_2} \\ & \leq f_{i-1,j_1}+w_{j_1,i_2}+f_{i-1,j_2}+w_{j_2,i_1} \\ & =A_{i_2,j_1}+A_{i_1,j_2} \end{aligned}\]其中运用了 \(w\) 的四边形不等式。
- \(f_{i}=\min\limits_{1 \leq j < i}{f_{j}+w_{j,i}}\)
此时同样可以构造矩阵 \(A\)：
那么 \(f_{x}=A_{x,\min_{x}(A)}\)，在矩阵 \(A\) 满足四边形不等式时可以快速计算。由于转移时 \(f\) 未知，我们不妨将其称为在线决策单调性。
-
定理 0.4：在上述在线决策单调性问题中，若 \(w\) 满足四边形不等式，则 \(A\) 也满足四边形不等式。
证明：同离线决策单调性问题，不再赘述。
一、决策单调性的决策点计算
为了避免输入成为瓶颈，以下的矩阵默认可以在较快时间内预处理并单点查询。
分治
最为常见的方法。对于单调矩阵 \(A\)，定义分治过程 \(\texttt{solve}(l,r,L,R)\) 为计算 \(l\sim r\) 行的 \(\min_{i}(A)\)，且已知它们的范围在 \([L,R]\) 内。
那么找到中点 \(mid=\lfloor \frac{l+r}{2} \rfloor\)，暴力在 \([L,R]\) 内计算出 \(M=\min_{mid}(A)\)，然后递归 \(\texttt{solve}(l,mid-1,L,M)\) 与 \(\texttt{solve}(mid+1,r,M,R)\)。递归边界为 \(l>r\) 或 \(L=R\)。
每次分治的复杂度为 \(\mathcal O(R-L)\)，分治树上每层的复杂度之和为 \(\mathcal O(m)\)，总时间复杂度为 \(\mathcal O(m\log n+n)\)。可以证明单调矩阵求解行最小值的复杂度下界为 \(\mathcal O(m\log n)\)。
分治法的缺点在于只能解决离线问题，然而它还有一个比较好的性质。当 \(A_{i,j}\) 无法直接求出，但拥有类似莫队的易加/易删性质，分治法可以同样在 \(\mathcal O((n+m)\log n)\) 的时间内求解。
具体而言，维护两个指针和它对应矩阵的值，单次分治的指针移动距离是 \(\mathcal O(r-l+R-L)\) 的，递归完左边到右边的时候指针移动距离同样是 \(\mathcal O(r-l+R-L)\) 的。
二分栈
在此之前，先说明几个完全单调矩阵的性质。
-
定理 1.1：对于 \(n\times m\) 的完全单调矩阵 \(A\) 和 \(1 \leq i < j \leq m\)，存在整数 \(0 \leq p_{i,j} \leq n\) 使得对于任意的 \(1 \leq k \leq n\)，\(A_{k,i} < A_{k,j}\) 当且仅当 \(k \leq p_{i,j}\)。
-
冗余元素：
对于 \(n\times m\) 的完全单调矩阵 \(A\)，定义某个元素是冗余的当且仅当它不是对应行的最小值所在位置。
-
冗余列：
对于 \(n\times m\) 的完全单调矩阵 \(A\)，定义某一列是冗余列当且仅当这一列上所有元素都是冗余元素。
-
定理 1.2：对于 \(n\times m\) 的完全单调矩阵 \(A\) 和 \(1 \leq i < j \leq m,1 \leq k \leq n\)，若 \(A_{k,i} < A_{k,j}\)，则 \(A_{1\sim k,j}\) 是冗余的，否则 \(A_{k\sim n,i}\) 是冗余的。
以上定理容易通过完全单调矩阵的定义说明其正确性。
二分栈是增量算法，其按顺序加入每一列，并用栈维护所有的非冗余列。由于单调性，对于第 \(j\) 列，若它不是冗余的，则存在区间 \([l_j,r_j]\) 使得这些行的目前最小值所在列都是 \(j\)。
当加入新的一列 \(j\) 时，不断取出栈顶元素，不妨设当前栈顶为第 \(top\) 列。若 \(A_{l_{top},top} \geq A_{j,top}\)，则说明第 \(top\) 列是冗余的，将其弹出栈；否则二分计算 \(p_{top,j}\)，将第 \(top\) 列的区间设为 \([l_{top},p_{top,j}]\)，第 \(j\) 列的区间设为 \([p_{top,j}+1,r_{top}]\)。时间复杂度 \(\mathcal O(m\log n)\)。
二分栈可以解决在线决策单调性问题，但是只适用于完全单调矩阵。
SMAWK
求解行最小值位置的时候，如果行少但列多，那么有很多列是冗余的。于是考虑实现子过程 \(\texttt{reduce(A)}\)，将 \(n\times m\) 的完全单调矩阵通过删除冗余列得到 \(n\times \min(n,m)\) 的矩阵。
reduce 操作流程如下：
-
初始定义 \(k=1\)。
-
若 \(n \geq m\) 则结束过程，否则比较 \(A_{k,k}\) 和 \(A_{k,k+1}\)。
-
若 \(A_{k,k} \geq A_{k,k+1}\)，则第 \(k\) 列为冗余列，删除第 \(k\) 列并且令 \(k \leftarrow \max(k-1,1)\)，回到第 \(2\) 步。
-
若 \(A_{k,k} < A_{k,k+1}\) 且 \(k<n\)，则令 \(k \leftarrow k+1\)，回到第 \(2\) 步。
-
若 \(A_{k,k} < A_{k,k+1}\) 且 \(k=n\)，则第 \(n+1\) 列为冗余列，删除第 \(n+1\) 列，回到第 \(2\) 步。
第 \(4,5\) 步很好理解，考虑第 \(3\) 步的正确性。
在前一轮中，已经确定了 \(A_{k-1,k-1}<A_{k-1,k}\)，故 \(A_{1\sim k-1,k}\) 是冗余的；而现在又有 \(A_{k,k} \geq A_{k,k+1}\)，所以 \(A_{k \sim n,k}\) 是冗余的，第 \(k\) 列是冗余列，可以删除。同时为了确保每次这么做的正确性，需要让 \(k\) 退回到 \(k-1\)。
至于时间复杂度，每次要么 \(k\) 加一，要么删除一列并让 \(k\) 至多减一，\(k\) 的最大值为 \(n\)，故时间复杂度为 \(\mathcal O(n+m)\)。实现可以使用链表维护列。
SMAWK 算法是一种基于 reduce 操作的递归算法，核心思路是只需要确定所有偶数行的最小值位置，就可以根据单调性 \(\mathcal O(m)\) 求出奇数行的最小值位置。
每次在递归之前用 reduce 操作让 \(m\) 变成 \(\min(n,m)\)，就可以使得 \(m\) 与 \(n\) 同阶，复杂度变成 \(\mathcal O(n+m)\)。
实际上当 \(m<n\) 时需要递归 \(\log\frac{n}{m}\) 轮才能进入 \(n \leq m\) 的情况，复杂度为 \(\mathcal O(n+m(1+\max(0,\log\frac{n}{m})))\)。然而 \(m\times \log\frac{n}{m} < m \times \frac{n}{m} = n\)，所以还是线性。
Wilber
SMAWK 只能解决离线决策单调性问题，我们需要一些支持在线的算法。
回顾一下在线决策单调性的问题：
其矩阵 \(A\) 需要满足四边形不等式。Wilber 算法如下：
-
初始时定义 \(r=c=1\)，算法中满足 \(\min_{1 \sim c}(A)\) 已经确定且 \(\min_{c+1}(A) \geq r\)。\(c=n\) 则算法结束。
-
设 \(p=\min(n,c+(c-r+1))\)，先用 \(f_{r\sim c}\) 去直接转移 \(f_{c+1\sim p}\)，即用 SMAWK 计算 \(A_{[c+1 \sim p],[r \sim c]}\) 中的行最小值作为 \(f\) 的估计值，记为 \(g_{c+1 \sim p}\)。
-
当然这是不准确的，于是考虑用这个估计值 \(g_{c+1 \sim p}\) 再做一次转移，得到二次估计值 \(h_{c+1,p}\)。
-
若对于所有 \(c+1 \leq i \leq p\)，都有 \(g_i \leq h_i\)，则所有的 \(g\) 都是准确的，令 \(c \leftarrow p\) 并回到第 \(2\) 步。
-
否则找到最小的 \(t\) 使得 \(g_t > h_t\)，此时 \(c+1 \sim t-1\) 的 \(g\) 是准确的，而 \(t\) 的 \(h\) 是准确的，且 \(\min_{t}(A) \geq c+1\)。令 \(r \leftarrow c+1,c \leftarrow t\)，并回到第 \(2\) 步。
正确性显然，考虑时间复杂度。设势能为 \(r+c\)，由于 \(p-c=c-r+1\)，所以第 \(2,3\) 步的时间复杂度均为 \(\mathcal O(c-r)\)。如果进入第 \(4\) 步，则势能增加 \(p-c=c-r+1\)；如果进入第 \(5\) 步，则势能增加 \(t-r+1\)，由于 \(t > c\)，所以至少增加了 \(c-r+1\)，均摊正确。因为 \(r+c \leq 2n\)，所以时间复杂度 \(\mathcal O(n)\)。
Eppstein
考虑如下的“交错动态规划”：
其中 \(w_{i,j},w'_{i,j}\) 均满足四边形不等式。如果用 Wilber 算法解决问题，那么 \(f\) 和 \(g\) 就需要同步求解。不妨假设第一次出现二次估计值才正确的位置是 \(t\)，可能 \(f\) 已经是二次估计值，但 \(g\) 还是一次估计值，这时就不能令 \(r \leftarrow c\)，因为 \(g\) 的转移点可能还 \(< c\)。但这样一来时间复杂度就无法均摊了，于是后来 Eppstein 改进了此算法。
我们在下面只考虑 \(f\) 的计算，但注意 \(g\) 的计算在同时进行。Eppstein 算法流程如下：
-
初始时定义 \(r=c=1\)，算法保证 \(f_{1\sim c},g_{1\sim c}\) 已经求出。维护数组 \(E_{1\sim n}\)，满足 \(f_i=\min(E_i,\min\limits_{r \leq j < i}{g_j+w_{j,i}})\)，即用 \(E\) 存一下 \(<r\) 的位置对后面的影响。
-
设 \(p=\min(n,c+(c-r+1))\)，同样用 \(f_{r\sim c}\) 去估计 \(f_{c+1\sim p}\)，SMAWK，与 \(E_{c+1\sim p}\) 取最小值得到估计值 \(h_{c+1\sim p}\)。
-
接着对所有 \(c+1 \leq i \leq p\) 计算 \(v_i=\max\limits_{i < j \leq p}{h_j-w_{i,j}}\)，表示 \(g_i\) 小到多少会估计错误。这是完全单调矩阵，SMAWK。设初始 \(k=c\) 表示已经计算完的位置。
-
\(k \leftarrow k+1\) 并确定 \(f_k\) 的真实值即为估计值。若 \(k=p\)，则令 \(c \leftarrow p\) 并回到第 \(2\) 步。
-
若 \(g_k \geq v_k\)，则此时不会导致后面估计错误，回到第 \(4\) 步。
-
否则此时 \(g_k\) 会破坏后面的估计，令 \(\forall i \in [c+1,p],E_i \leftarrow h_i,r \leftarrow c+1,c \leftarrow k\)，回到第 \(2\) 步。
为什么最后一步只需要更新 \(E_{c+1\sim p}\) 呢？因为我们已经知道 \(g_k\) 会破坏 \((k,p]\) 的估计，即存在 \((k,p]\) 的某个位置转移点 \(\geq k\)，那么 \(f_{r\sim c}\) 便不会对 \(>p\) 的位置产生贡献。
注意上面 \(f\) 和 \(g\) 的 \(r,c,E_i,v_i\) 都是不同的，只是按照 \(k\) 的进度来同时求出 \(f_k,g_k\)。
时间复杂度和 Wilber 算法一样，均摊 \(\mathcal O(n)\)，区别在于 Eppstein 算法抛弃了后续转移点必须 \(\geq r\) 的条件，使用了 \(E\) 数组记录转移点 \(<r\) 的情况，且巧妙地使用 \(v\) 数组代替无法计算的二次估计值。
同时 Eppstein 算法可以按照 \(f_1,f_2,\cdots,f_n\) 的顺序一个个确定值，而不像 Wilber 算法一次性确定某个连续区间的值。这样 Eppstein 算法可以支持多个 dp 交错转移。
二、二维决策单调性
最优搜索树问题
俗称石子合并，本质上是给出每个元素询问次数，要求建立一棵搜索树使得使得查询时间和最小。转移方程如下：
-
区间包含单调性：
对于 \(n\times n\) 的方阵 \(A\)，若对于所有的 \(i \leq i' \leq j' \leq j\)，都有 \(A_{i,j} \geq A_{i',j'}\)，则称 \(A\) 满足区间包含单调性。
若 \(w\) 权值组成的矩阵满足四边形不等式和区间包含单调性，则可以将复杂度从 \(\mathcal O(n^3)\) 降低。
朴素动态规划算法的加速
以下默认 \(w\) 权值组成的矩阵满足四边形不等式和区间包含单调性。
-
定理 2.1：矩阵 \(\{f_{i,j}\}\) 满足四边形不等式。
证明：只需证明对所有的 \(i \leq i' \leq j \leq j'\) 都有 \(f_{i,j}+f_{i',j'} \leq f_{i,j'}+f_{i',j}\) 即可。
设 \(f_{i,j,y}\) 表示决策点为 \(y\) 时 \(f_{i,j}\) 的结果，即 \(w_{i,j}+f_{i,y}+f_{y+1,j}\)。
对 \(j'-i\) 归纳，当 \(j'-i-1\) 成立时，讨论 \(j'-i\) 是否成立。
-
当 \(i=i'\) 或 \(j=j'\) 时，显然成立。
-
当 \(i'=j\) 时，需要证明 \(f_{i,j}+f_{j,j'} \leq f_{i,j'}+f_{j,j}\)。不妨设 \(f_{i,j'}\) 的最优转移点为 \(y\)，且 \(y<j\)，则：
\[\begin{aligned} f_{i,j}+f_{j,j'} & \leq f_{i,j,y}+f_{j,j'} \\ & =(w_{i,j}+f_{i,y}+f_{y+1,j})+f_{j,j'} \\ & \leq w_{i,j'}+f_{i,y}+(f_{y+1,j}+f_{j,j'}) \\ & \leq w_{i,j'}+f_{i,y}+(f_{y+1,j'}+f_{j,j}) \\ & = f_{i,j'}+f_{j,j} \end{aligned}\]其中运用了 \(w\) 的区间包含单调性和 \(\leq j'-i-1\) 的归纳假设。\(y \geq j\) 时拆 \(f_{j,j'}\) 同理。
-
当 \(i' \neq j\) 时，设 \(f_{i,j'}\) 和 \(f_{i',j}\) 的最优转移点分别为 \(y\) 和 \(z\) 且 \(y \leq z\)，则：
\[\begin{aligned} f_{i,j}+f_{i',j'} & \leq f_{i,j,y}+f_{i',j',z} \\ & =(w_{i,j}+f_{i,y}+f_{y+1,j})+(w_{i',j'}+f_{i',z}+f_{z+1,j'}) \\ & \leq (w_{i,j'}+w_{i',j})+(f_{i,y}+f_{i',z})+(f_{y+1,j}+f_{z+1,j'}) \\ & \leq (w_{i,j'}+w_{i',j})+(f_{i,y}+f_{i',z})+(f_{y+1,j'}+f_{z+1,j}) \\ & = f_{i,j'}+f_{j,j} \end{aligned}\]其中运用了 \(w\) 的四边形不等式和 \(\leq j'-i-1\) 的归纳假设。\(y > z\) 时同理将 \(f_{i,j}+f_{i',j'}\) 放缩至 \(f_{i,j,z}+f_{i',j',y}\)，对 \((f_{i,z}+f_{i',y})\) 用四边形不等式即可。
-
-
定理 2.2：设 \(f_{i,j}\) 最小的最优转移点为 \(K_{i,j}\)，则有 \(K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j}\)。
这里只证明 \(K_{i,j-1} \leq K_{i,j}\)，右边是一样的。
对于一个定值 \(i\)，考虑构造 \(n\times n\) 的矩阵 \(A\)：
\[A_{x,y}=\begin{cases} w_{i,x}+f_{i,y}+f_{y+1,x}, & i \leq y < x \\ +\infty, & \texttt{otherwise} \end{cases}\]可以证明 \(A\) 为蒙日阵，具体证明方法会在第四章节介绍蒙日阵中讲到，大家也可以先自行思考。因此有 \(\min_{j-1}(A) \leq \min_{j}(A)\)，即 \(K_{i,j-1} \leq K_{i,j}\)。
有了二维上的单调性，就可以按照区间长度顺序计算 \(f\) 和 \(K\)。初始时 \(K_{i,i}=i\)，在计算 \(K_{i,j}\) 时，由于 \(K_{i,j-1}\) 和 \(K_{i+1,j}\) 已经确定，于是可以根据 \(K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j}\) 来暴力枚举算出 \(K_{i,j}\)。计算长度为 \(len\) 的总时间复杂度为 \(\sum\limits_{i=1}^{n-len+1}{(K_{i+1,i+len-1}-K_{i,i+len-2})}=K_{n-len+2,n}-K_{1,len-1}=\mathcal O(n)\)，总时间复杂度 \(\mathcal O(n^2)\)，常数较小。
多叉树拓展
即求最优 \(k\) 叉搜索树，相当于把 \(1\) 个断点变成 \(k-1\) 个断点，转移式如下：
暴力做的复杂度为 \(\mathcal O(n^2k)\)。实际上可以用倍增求出 \(f^{2^k}_{i,j}\)，时间复杂度 \(\mathcal O(n^2\log k)\)。好像没什么用。
三、决策单调性最短路问题
定义及基本算法
考虑经典的 DAG 最短路问题：给定 \(n\) 个点的 DAG，对于 \(i<j\) 时有边权 \(w_{i,j}\)，求 \(1\) 到 \(n\) 经过 \(k\) 条边的最短路。
写成动态规划就是熟悉的式子：
暴力求解的复杂度 \(\mathcal O(n^2k)\)。当 \(w\) 满足四边形不等式时，这是一个离线决策单调性问题，可以用 SMAWK 做到 \(\mathcal O(nk)\)。
下文将继续探讨一些拓展和优化。
答案凸性
-
引理 3.1：记 \(f(k)=f_{k,n}\)，则 \(\forall 1 \leq s < r < t \leq n-1,f(s)+f(t) \geq f(r)+f(s+t-r)\)。
证明：设 \(f(s)\) 的其中一个最优方案是 \(p_1,p_2,\cdots,p_{s+1}\)，\(f(t)\) 的其中一个最优方案是 \(q_1,q_2,\cdots,q_{t+1}\)。
设 \(v=r-s\)，若存在 \(i \in [1,s]\) 使得 \(p_{i} \leq q_{i+v} < q_{i+v+1} \leq p_{i+1}\)，那么可以构造两条路径如下：
-
\(p_1,p_2,\cdots,p_i,q_{i+v+1},\cdots,q_{t+1}\)，长度为 \(s+t-r\)
-
\(q_1,q_2,\cdots,q_{i+v},p_{i+1},\cdots,p_{s+1}\)，长度为 \(r\)
而根据四边形不等式 \(w_{p_i,q_{i+v+1}}+w_{q_{i+v},p_{i+1}} \leq w_{p_i,p_{i+1}}+w_{q_{i+v},q_{i+v+1}}\)，可得 \(f(s)+f(t)\) 不比这两条路径长度和小，即不比 \(f(r)+f(s+t-r)\) 小。
那么只需要说明一定存在这样的 \(i\) 即可。
考虑以 \(p_i\) 作为分割点将 \((1,n]\) 分为 \(s\) 段，其中第 \(i\) 段区间为 \((p_i,p_{i+1}]\)。设 \(a_i(1 \leq i \leq s+1)\) 表示 \(q_{i+v}\) 在哪一段，\(b_i=a_i-i\)。
由于 \(v \geq 1\)，所以 \(a_{v+1} \geq 1\)，\(b_1 \geq 0\)。同时 \(b_{s+1}=-1,b_i-b_{i-1} \geq -1\)，所以 \(b\) 序列中一定有 \(-1\)。取最前面的 \(-1\)，假设是 \(b_{i+1}\)，那么一定有 \(b_i=0\)，即 \(a_i=a_{i+1}=i\)，根据定义有 \(p_i < q_{i+v} < q_{i+v+1} \leq p_{i+1}\)，得证。
-
-
定理 3.2：\(f\) 在定义域上是下凸函数，即 \(\forall k\in[2,n-2],f(k+1)-f(k) \geq f(k)-f(k-1)\)。
代入上面的引理即可证明。
wqs 二分及其方案构造
由于 \(f\) 的斜率是单增的，于是可以二分斜率，转为求截距最小值所在点。对于函数 \(y=kx+b\)，那么 \(b=y-kx\)，可以看作每走一步都要花费 \(k\) 的代价，其中 \(k\) 为二分的斜率。此问题为在线决策单调性问题，可以用 Wilber 做到 \(\mathcal O(n)\)。总复杂度 \(\mathcal O(n\log V)\)。
然而要构造 \(f(k)\) 的方案时，有可能出现 \(f(k+1)-f(k)=f(k)-f(k-1)\) 的情况，此时怎么切都切不到 \(k\)，这时需要额外构造。（前情提要，讲的很难绷）
设答案斜率为 \(x\)，用 \(x-\epsilon\) 切到的是左端点 \((p,f(p))\)，用 \(x+\epsilon\) 切到的是右端点 \((q,f(q))\)，那么对于 \(r \in [p,q]\) 都有 \(f(r)=f(p)+(r-p)x\)。
先用两次动态规划把 \(f(p)\) 和 \(f(q)\) 的最优路径求出来，然后用引理的构造方式得到长度分别为 \(k\) 和 \(p+q-k\) 的路径。设这两条路径的答案分别为 \(f'(k)\) 和 \(f'(p+q-k)\)，那么就有以下几点：
-
\(f'(k) \geq f(k) = f(p)+(k-p)x\)
-
\(f'(p+q-k) \geq f(p+q-k) = f(p)+(q-k)x\)
-
\(f'(k)+f'(p+q-k) \leq f(p)+f(q) = 2f(p)+(q-p)x\)
于是就有 \(f'(k)=f(k),f'(p+q-k)=f(p+q-k)\)，构造的路径均为最优路径。
路径单调性与不交性
-
定理 3.3：设 \(x_1,\cdots,x_{k+1}\) 为 \(p_1 \sim q_1\) 长度为 \(k\) 的字典序最小的最短路，\(y_1,\cdots,y_{k+1}\) 为 \(p_2 \sim q_2\) 长度为 \(k\) 的字典序最小的最短路，且 \(p_1 \leq p_2,q_1 \leq q_2\)，则 \(\forall i\in [1,k+1],x_i \leq y_i\)。
证明：考虑反证。找到第一个 \(i\) 满足 \(x_i > y_i\)，再找到之后第一个 \(j\) 满足 \(x_j \leq y_j\)，则将路径调整为这两条：
-
\(x_1,\cdots,x_{i-1},y_i,\cdots,y_{j-1},x_j,\cdots,x_{k+1}\)
-
\(y_1,\cdots,y_{i-1},x_i,\cdots,x_{j-1},y_j,\cdots,y_{k+1}\)
由于四边形不等式，那么这两条路径的答案之和不会变大，而 \(p_1 \sim q_1\) 的路径字典序变小了，矛盾。
-
-
定理 3.4：设 \(x_1,\cdots,x_{k+1}\) 为 \(1 \sim n\) 长度为 \(k\) 的字典序最小的最短路，\(y_1,\cdots,y_{k+2}\) 为 \(1 \sim n\) 长度为 \(k+1\) 的字典序最小的最短路，则 \(\forall i \in [1,k+1],y_i \leq x_i \leq y_{i+1}\)。
证明：注意到 \(y_{1 \sim k+1}\) 与 \(y_{2 \sim k+2}\) 均为长为 \(k\) 的字典序最小的最短路，把它们分别于 \(x\) 应用上面的路径单调性即可证明。
两个性质分别长这样：
-
定理 3.5：设 \(x_1,\cdots,x_{k+1}\) 为 \(1 \sim n\) 长度为 \(k\) 的字典序最小的最短路，则对于任意 \(1 \leq l \leq r \leq n\)，\(x_l,\cdots,x_r\) 为 \(x_l \sim x_r\) 的长度为 \(r-l\) 的字典序最小的最短路。
正确性显然，否则 \(x_1,\cdots,x_{k+1}\) 不是 \(1 \sim n\) 长度为 \(k\) 的字典序最小的最短路。
-
定理 3.6：对于任意 \(i,j\)，有 \(K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j}\)。
证明：对于左边，均为长度为 \(i\) 的路径，根据路径单调性可证 \(K_{i,j-1} \leq K_{i,j}\)；对于右边，均为 \(1 \sim j\) 的路径，根据路径不交性可证 \(K_{i,j} \leq K_{i+1,j}\)。
有了这个性质，我们就可以用常数较小的二维决策单调性方法来代替 SMAWK，时间复杂度同样为 \(\mathcal O(nk)\)。
环上邮局
原题：XIX Open Cup Grand Prix of Zhejiang I
\(n\) 个点放在一个长度为 \(L\) 的环上，你需要把它们分成恰好 \(k\) 段，每段的代价是该段中所有点到中位数的距离和。求最小代价并输出方案。
首先可以枚举每个位置作为断点，断环成链，变成经典的 DAG 最短路问题，暴力求解可得总时间复杂度为 \(\mathcal O(n^3k)\)。
接下来，我们会一步步地通过观察性质来降低时间复杂度。
- \(\mathcal O(n^2k)\)
注意到 \(w_{i,j}\) 可以通过预处理前缀和来做到 \(\mathcal O(1)\) 计算，且其满足四边形不等式。
证明：只需对所有 \(i<j\)，证明 \(w_{i,j}+w_{i+1,j+1} \leq w_{i,j+1}+w_{i+1,j}\) 即可。
设 \(x_i\) 为第 \(i\) 个点的坐标，\(P_{i,j}\) 为区间 \([i,j]\) 的中位数，若区间长度为偶数则可以在中间两个数之间任取。那么可以通过调整使得 \(P_{i,j}=P_{i,j+1},P_{i+1,j}=P_{i+1,j+1}\)。
式子两边抵消之后只剩下 \(x_{j+1}-P_{i+1,j+1} \leq x_{j+1}-P_{i,j+1}\)，显然正确。
于是可以用 SMAWK 或二维决策单调性来优化到单次 \(\mathcal O(nk)\)，总时间复杂度 \(\mathcal O(n^2k)\)。
- \(\mathcal O(n^2\log V)\)
由于 \(w\) 满足四边形不等式，答案是下凸函数，于是可以使用 wqs 二分+Wilber 做到单次 \(\mathcal O(n\log V)\)，总时间复杂度 \(\mathcal O(n^2\log V)\)。
- \(\mathcal O(n\log V+n^2)\)
暴力枚举断点好像很蠢，考虑优化。
先断环成链，将它复制无限份，然后 \(\mathcal O(n\log V)\) 跑出 \(0\to L\) 的字典序最小的最短路 \(x_1=0,x_2,\cdots,x_{k+1}=L\)。
设全局字典序最小的最短路为 \(y_1\in [0,L),y_2,\cdots,y_{k+1}=y_1+L\)，那么运用路径单调性有 \(\forall i\in [1,k+1],x_i \leq y_i\)。
接下来取路径 \(x_2,\cdots,x_{k+1},x_{k+2}=x_2+L\)，则可以证明 \(\forall i\in [1,k+1],y_i \leq x_{i+1}\)。
证明：首先 \(x_2,\cdots,x_{k+1}\) 为 \(x_2 \to L\) 的长为 \(k-1\) 的字典序最小的最短路，\(y_1,\cdots,y_k\) 为 \(y_1 \to y_k\) 的长为 \(k-1\) 的字典序最小的最短路。那么根据路径单调性，要么 \(\forall i\in [1,k],y_i \leq x_{i+1}\)，要么 \(\forall i\in [1,k],y_i \geq x_{i+1}\)。由于 \(y\) 为全局字典序最小的最短路，故 \(y_k<L=x_{k+1}\)，后者不成立，证毕。
于是就有 \(\forall i\in [1,k],x_i \leq y_i \leq x_{i+1}\)。取所有 \([x_i,x_{i+1}]\) 中点数最少的一段来枚举，最多 \(\frac{n}{k}\) 个点，每次跑 \(\mathcal O(nk)\) 的动态规划，总时间复杂度为 \(\mathcal O(n\log V+n^2)\)。
- \(\mathcal O(n(\log n+\log V))\)
根据上面的分析，有 \(y_i\in [x_i,x_{i+1}]\)，且由于路径单调性，当 \(y_1\) 增大时 \(y_i(1 \leq i \leq k+1)\) 不会变小，于是可以分治。
设 \(\texttt{solve}(l_1,r_1,l_2,r_2,\cdots,l_k,r_k)\) 表示计算 \(k\) 个断点在各自范围内的最优解，每次取 \([l_1,r_1]\) 的中点 \(\frac{l_1+r_1}{2}\) 为第一个断点，然后做 \(k-1\) 次 SMAWK 计算剩余 \(k-1\) 个断点的最优解和方案，递归到两边进行处理。
单次复杂度为 \(\mathcal O(\sum{r_i-l_i})\)，那么分治树上每层的时间复杂度之和为 \(\mathcal O(\sum{x_{i+1}-x_i})=O(n)\)，总分治时间复杂度就是 \(\mathcal O(n\log n)\) 的了……吗？
实际上，每次分治都至少有一个 \(\mathcal O(k)\) 的复杂度，分治树上的总点数为 \(\mathcal O(n)\)，于是复杂度就变成了 \(n\log n+\mathcal O(nk)\)。
还是考虑取所有 \([x_i,x_{i+1}]\) 中点数最少的一段来分治，将它转到第一个区间，然后总点数就变成了 \(\mathcal O(\frac{n}{k})\)，总时间复杂度为 \(\mathcal O(n(\log n+\log V))\)。
四、四边形不等式的其他应用
蒙日阵的生成及其性质
-
蒙日矩阵乘法：
设 \(A,B\) 为蒙日阵，则定义蒙日矩阵乘法为 \(C_{i,j}=\min_{k}{A_{i,k}+B_{k,j}}\)，即 \((min,+)\) 矩乘。
-
定理 4.1：若矩阵 \(A,B\) 为蒙日阵，则 \(C=AB\) 也为蒙日阵。
证明：只需证明 \(\forall i_1 \leq i_2,j_1 \leq j_2\) 均满足四边形不等式。设 \(C_{i_1,j_2}\) 取到最小值的位置是 \(k_1\)，\(C_{i_2,j_1}\) 取到最小值的位置是 \(k_2\)，且 \(k_1 \leq k_2\)，则：
\[\begin{aligned} C_{i_1,j_1}+C_{i_2,j_2} & \leq (A_{i_1,k_1}+B_{k_1,j_1})+(A_{i_2,k_2}+B_{k_2,j_2}) \\ & =(A_{i_1,k_1}+A_{i_2,k_2})+(B_{k_1,j_1}+B_{k_2,j_2}) \\ & \leq (A_{i_1,k_1}+A_{i_2,k_2})+(B_{k_1,j_2}+B_{k_2,j_1}) \\ & =(A_{i_1,k_1}+B_{k_1,j_2})+(A_{i_2,k_2}+B_{k_2,j_1}) \\ & =C_{i_1,j_2}+C_{i_2,j_1} \end{aligned}\]\(k_2 \leq k_1\) 同理。
那么以下矩阵均为蒙日阵：
-
\(A+B\)
-
\(AB\)
-
\(\lambda A\)，其中 \(\lambda \geq 0\)
-
\(A^{T}\)
第 \(1,3,4\) 点可以通过四边形不等式的定义简单证明，第 \(2\) 点的证明已在上面给出。因此可以使用一些常见的蒙日阵进行随机线性组合得到随机性较强的蒙日阵。有了这些基础，就可以快速证明 定理 2.2 的内容了。
这里举一些常见蒙日阵的例子，假设以下蒙日阵的大小为 \(n\times m\)：
-
\(a_{x,y}=\min(x,y)\)
-
\(a_{x,y}=\max(x,y)\)
-
\(a_{x,y}=xy\)
-
\(a_{x,y}=|x-y|^p(p \leq 1)\)
-
\(a_{x,y}=\sum\limits_{i=1}^{x}\sum_\limits{j=y}^{m}{d_{x,y}}\)，其中 \(d\) 是一个 \(n\times m\) 的非负元素矩阵
-
\(a_{x,y}=[x=k]v_k\)
-
\(a_{x,y}=[y=k]v_k\)
-
\(a_{x,y}=f(x-y)\)，其中 \(f(x)\) 是下凸函数
以及你所见到的所有四边形不等式优化 dp 题目里的权矩阵。
-
次模函数：
对于有限集 \(S\) 和定义域在 \(2^S\) 的函数 \(f\)，若 \(\forall X,Y \in S,f(X)+f(Y) \geq f(X \cup Y)+f(X \cap Y)\)，则称 \(f\) 是次模函数。
对于定义在集合 \(S\) 的次模函数 \(f\) 和由 \(S\) 集合构成的排列 \(d_1,\cdots,d_{|S|}\)，考察 \(|S| \times |S|\) 的矩阵 \(A\)：
则 \(A\) 满足四边形不等式，此时 \(f\) 对应到 \(\max\) 问题。
以下举一些次模函数的例子：
-
集合并函数是次模函数
-
拟阵的秩函数是次模函数（2018 论文）
-
点集的割权函数是次模函数（2016 论文）
连续子矩阵最小值查询
原题：暂无
给定 \(n\times n\) 的蒙日阵 \(A\)，保证可以快速预处理后 \(\mathcal O(1)\) 计算单点值。\(q\) 次询问，每次询问 \(A_{[l_1\sim r_1],[l_2\sim r_2]}\) 的最小值。
先考虑 \(l_2=r_2\) 的子问题。对行建立线段树，对于一段行区间 \([l,r]\)，每一列的最小值所在行单调不降，所以只需要维护 \(\mathcal O(r-l)\) 个区间，其中每一段区间的列的最小值所在行相同。
合并的话，由于列最小值所在行单调，所以肯定是一段前缀从左儿子继承过来，另一段从右儿子继承过来，二分一下即可。预处理总复杂度为 \(\mathcal O(n\log n)\)。
询问时找到 \([l_1,r_1]\) 对应的线段树节点，然后对每个节点二分出 \(l_2\) 列的最小值，单次复杂度 \(\mathcal O(\log^2 n)\)。使用分散层叠可以优化到 \(\mathcal O(\log n)\)。
把矩阵转置一下就可以做 \(l_1=r_1\)。
对于原问题，还是建立行线段树。对于每个线段树节点 \([l,r]\)，维护其每一段的最小值 \(v_i\)，即 \(A_{[i\sim i],[L_i\sim R_i]}\) 的最小值。由于左右儿子合并时最多有 \(\mathcal O(1)\) 段发生变化，于是只用求 \(\mathcal O(n)\) 次行最小值，预处理复杂度 \(\mathcal O(n\log n)\)。
考虑询问，找到线段树上对应的 \(\log n\) 个区间。对于每个区间 \([l,r]\)，需要求出 \(A_{[l\sim r],[l_2\sim r_2]}\) 的最小值。对于那些整段都在 \([l_2,r_2]\) 里的段，可以直接调用 \(v_i\)，是一个区间 RMQ 问题，可以直接用树套树或者 \(\mathcal O(n)-\mathcal O(1)\) RMQ；否则最多只有 \(2\) 个不完整的段，可以直接查询行最小值，查询总时间复杂度 \(\mathcal O(q\log^2 n)\)。
复杂度瓶颈在于散段的查询，听说可以优化到 \(\mathcal O(q\log n)\)。
航天飞机调度
原题：uoj672
咕。
挑战旅行商
原题：暂无
给定 \(n\times n\) 的蒙日阵 \(A\)，满足 \(A_{i,i}=0\)，可以快速预处理后 \(\mathcal O(1)\) 计算单点值。求以该矩阵为邻接矩阵的带权有向图的边权和最小的哈密顿回路。
-
双调回路：
对于带权有向图 \(G\)，定义按照 \(n > i_1 > i_2 > \cdots > i_{k_1} > 1 < j_1 < j_2 < \cdots < j_{k_2} < n\) 顺序经过所有点的哈密顿回路为双调回路。
对于任意哈密顿回路的边权和最小值不易计算，但是对于双调回路的边权和最小值是容易计算的。
设 \(f_{i,j}\) 表示形如 \(i > p_1 > p_2 > \cdots > p_{k_1} > 1 < q_1 <q_2 < \cdots < q_{k_2} < j\) 的路径的边权和最小值，转移时根据 \(i\) 与 \(j\) 的差值来确定上一个点是 \(p_1\) 还是 \(q_{k_2}\)，当 \(|i-j|=1\) 时需要枚举。时间复杂度 \(\mathcal O(n^2)\)。
大家应该都知道下一步要证什么了。
-
定理 4.2：若带权有向图 \(G\) 的邻接矩阵是蒙日阵，则存在旅行商问题的一个解是双调回路。
证明：考虑归纳法，假设现在 \(n-1\) 已经成立。当 \(n\leq 3\) 时显然成立，否则考察某个不是双调回路的最优回路，存在某个点 \(p\) 使得前驱 \(pre_p<p\) 且后继 \(suf_p<p\)。
则根据四边形不等式有 \(w_{pre_p,suf_p}+w_{p,p} \leq w_{pre_p,p}+w_{suf_p,p}\)，将 \(p\) 拿出来，\(pre_p\) 接上 \(suf_p\) 后答案不会更大。此时图上剩下一个大小为 \(n-1\) 的哈密顿回路，根据假设可以把它调整为双调回路。
之后找到回路上的点 \(q\) 使得 \(q < p < suf_q\)，那么将 \(p\) 接到中间，根据四边形不等式有 \(w_{q,p}+w_{p,suf_q} \leq w_{q,suf_q}+w_{p,p}\)。由于 \(w_{p,p}=0\)，所以答案不会变得更大，且得到的是一个双调回路。
接下来考虑优化 \(\mathcal O(n^2)\) 的最优双调回路计算。
设 \(F_i=f_{i+1,i},G_i=f_{i,i+1}\)，那么答案就是 \(\min(F_{n-1}+w_{n_1,n},G_{n-1}+w_{n,n-1})\)，转移如下：
这是交错动态规划模型。考虑 \((n-1)\times (n-1)\) 的 \(F\) 转移矩阵 \(A\)：
注意到 \(A_{x,y}+A_{x+1,y+1}\) 与 \(A_{x+1,y}+A_{x,y+1}\) 的和式部分（即 \(\sum w_{k,k+1}\)）抵消掉了，只剩下 \(w_{y+1,x}+w_{y+2,x+1}\) 和 \(w_{y+1,x+1}+w_{y+2,x}\)。又因为 \(w\) 满足四边形不等式，所以 \(A\) 也满足四边形不等式。
同理，\(G\) 的转移矩阵也满足四边形不等式，预处理前缀和后可以 \(\mathcal O(1)\) 计算转移权值，于是用 Eppstein 算法可以做到时间复杂度 \(\mathcal O(n)\)。