四边形不等式和决策单调性

· · 算法·理论

下文中均讨论 \min 的情况。若为 \max，则所有关于 f 和 w 的不等式符号都要取反。

四边形不等式的定义

称 w 满足四边形不等式当且仅当所有 a,b,c,d 满足 a\le b\le c\le d，

w(a,d)+w(b,c)\ge w(a,c)+w(b,d)

也写作

w(a,d)-w(a,c)\ge w(b,d)-w(b,c)

即大区间差分大于等于小区间差分。

显然这个条件等价于，对于所有 a\le b 的 a,b，w(a,b+1)-w(a,b)\ge w(a+1,b+1)-w(a+1,b)，因为差分具有可加性、不等号具有传递性。此式也等价于 w 的二阶差分 \le0。

第一类 dp

f_i=\min_{j<i}\{f_j+w(j,i)\}

决策单调性及其证明

若 w 满足四边形不等式，则 f_i 的决策点 j 具有单调性。这里的单调性显然只有 j 随着 i 的增大而增大有意义，所以下文都不显式说明。

证明：考虑一个位置 i，它的最优决策是 j，这说明对于任意 k<j，f_j+w(j,i)\le f_k+w(k,i)。对于任意 i'>i，考虑证明 j 这个决策仍比 k 优。因为大区间差分大于等于小区间差分，而这里的 k 对应的是大区间，即 w(j,i')-w(j,i)\le w(k,i')-w(k,i)。将两个不等式相加，得 f_j+w(j,i')\le f_k+w(k,i')，这说明 j 成为最优决策后，k 永远不可能再成为最优决策。得证。

算法一：二分队列

该算法要求 w 满足四边形不等式。

按顺序枚举 i，求出 f_i 后，考虑 i 能成为后面哪些位置的决策点。根据上面关于决策单调性的证明，在 i 之后一定存在一个点 j，满足 j 之前 i 作为决策比 i 之前的决策都不优，j 之后 i 作为决策比 i 之前的决策都优。仅有 f 决策单调不足以推出这个结论，还需要 w 满足四边形不等式（或其他性质）。此时不妨暂时把 j 之后的决策都设为 i，之后遇到更优的再改。

具体地，维护一个队列，队列中每个位置是一个三元组 (l,r,k)，表示 [l,r] 内目前的最优决策点是 k。按顺序枚举每一个 i。求出 f_i 后，先尝试弹出队尾：若队尾是 (l,r,k)，则检查 l 处决策 i 是否比 k 优，如果优则弹出。直到无法弹出，此时在 [l,r] 中二分出最小的 j，满足 j 处 i 比 k 优。将队尾修改为 (l,j-1,k)，并再将 (j,n,i) 插入队尾。及时弹出队头，即可在枚举到 i 时快速找出最优决策。

算法二：Simplified LARSCH Algorithm by noshi91

该算法要求 w 满足四边形不等式，可以在 w 不支持随机访问只支持移动访问的情况下做到 \mathcal O(n\log n)。

考虑分治 solve(l,r)，过程中维护每个人的最优决策点 p_i。

先决条件：

p_r=\argmin_{j<l}\{f_j+w(j,r)\}

分治结束后需满足 [l,r] 中的 f_i,p_i 都被求出。

令 m=\lfloor\frac{l+r}{2}\rfloor。首先在 [p_{l-1},p_r] 中枚举 j，尝试用 j 更新 p_m。然后递归 solve(l,m)。然后在 [l,m] 中枚举 j，尝试用 j 更新 p_r。最后递归 solve(m+1,r)。

在只支持移动访问的情况下，全局维护一个指针，在进入和离开 solve(l,r) 时保证在 (p_{l-1},l)。对于 ([p_{l-1},p_r],m) 调用该指针，对于 ([l,m],r) 直接新建一个指针进行移动即可。

算法正确性显然，下面分析复杂度。容易发现 solve(l,r) 花费的复杂度是 \mathcal O(r-l+p_r-p_{l-1})。r-l 部分的总和显然是 \mathcal O(n\log n)。关于 p_r-p_l，在分治树的同一层中，所有 (p_l,p_r] 无交，所以这部分的总和也是 \mathcal O(n\log n)。

总时间复杂度 \mathcal O(n\log n)。

算法三：LARSCH Algorithm

该算法要求 w 满足四边形不等式，可以在 w 支持随机访问的情况下做到 \mathcal O(n)。

笔者也不会，读者可自行阅读：

注：此方程无法使用第三类 dp 中的分治算法，因为只有求出 i 之前的所有 dp 值后，f_i 的决策点和值才能被确定。

第二类 dp

f_{l,r}=\min_{l\le i<r}\{f_{l,i}+f_{i+1,r}\}+w(l,r)

决策单调性及其证明

记 p_{l,r} 为 f_{l,r} 的最优决策点，我们需要的决策单调性是 l 固定时，p_{l,r} 随 r 的增大而增大，且 r 固定时，p_{l,r} 随 l 的增大而增大。观察到，l 固定时，这个式子和上面一维的很像，只是 \min 中的 w(j,i) 变成了 f_{i+1,r}。如果 f 也满足四边形不等式，那么通过一样的过程可以证明决策单调性。r 固定时同理，读者可尝试自行推导。

有定理：若 w 满足四边形不等式，且对于所有 a\le b\le c\le d 的 a,b,c,d 有 w(b,c)\le w(a,d)（称为“区间包含单调性”），那么 f 满足四边形不等式。

证明：

从差分的角度不好考虑，所以采用这个形式：

f_{a,d}+f_{b,c}\ge f_{a,c}+f_{b,d}

首先，这四个形如 f_{l,r} 的东西里都有一个 w(l,r)，而 w 满足四边形不等式，所以可以将它全部去掉，只剩下四个 \min。

记 p=p_{a,d},q=p_{b,c}。注意，若 b=c 则 q 无意义，所以下面需要单独讨论 b=c 的情况。这里先证明 b<c 的情况。不妨设 p\le q。读者可模仿下面的证明自行推导 p>q 时的情况。

易知 p 在 [a,c] 中，q 在 [b,d] 中，所以 p 和 q 是 f_{a,c} 和 f_{b,d} 的任意一个决策，所以有 f_{a,p}+f_{p+1,c}+w(a,c)\ge f_{a,c}，f_{b,d} 同理。于是，可以要证的不等式右边进行放大，变为：

f_{a,p}+f_{p+1,d}+f_{b,q}+f_{q+1,c}\ge f_{a,p}+f_{p+1,c}+f_{b,q}+f_{q+1,d}

消去相同的项，得：

f_{p+1,d}+f_{q+1,c}\ge f_{p+1,c}+f_{q+1,d}

这个就是四边形不等式的形式，只是规模小了一点，所以可以关于 d-a 的大小归纳，即可证明。归纳边界即为 a=b=c=d，结论成立是非常显然的。

还剩 b=c 的情况，将原来的 a\le b=c\le d 变为 a\le b\le c，于是我们要证：

f_{a,c}+f_{b,b}\ge f_{a,b}+f_{b,c}

这次不消去四个 w。令 p=p_{a,c}。不妨设 p<b，p\ge b 同理。取 p 为 f_{a,b} 的一个决策点（不一定最优），则不等式变为：

f_{a,p}+f_{p+1,c}+w(a,c)+f_{b,b}\ge f_{a,p}+f_{p+1,b}+w(a,b)+f_{b,c}

消去相同项，又因为 w(a,c)\ge w(a,b)，所以不等式变为：

f_{p+1,c}+f_{b,b}\ge f_{p+1,b}+f_{b,c}

形式相同，可以归纳。

得证。所以 f 满足四边形不等式，决策对于两维都有单调性。

算法

考虑对于每个 l,r，从 p_{l,r-1} 到 p_{l+1,r} 枚举 i，求出 f 并记录下 p。这个算法的时间复杂度为：

\begin{aligned}&\sum_{1\le l<r\le n}p_{l+1,r}-p_{l,r-1}\\=&\sum_{2\le l\le r\le n}p_{l,r}-\sum_{1\le l\le r<n}p_{l,r}\\=&\sum_{2\le l\le n}p_{l,n}-\sum_{1\le r<n}p_{1,r}\\=&\mathcal O(n^2)\end{aligned}

第三类 dp

f_{i,j}=\min_{k\le j}\{f_{i-1,k}+w(k,j)\}\quad (1\le i\le m,1\le j\le n)

决策单调性及其证明

用第一类 dp 的方法可以证明决策关于第二维单调。想要证明第一维单调，需要证明 f 满足一个类似四边形不等式的东西：对于任意满足 a<b,c<d 的 a,b,c,d（无需满足 b<c），f_{a,d}+f_{b,c}\ge f_{a,c}+f_{b,d}。

类似第二类 dp 的证法，但是这次对 b 归纳。b=1 时不等式左右两边相等，结论成立。

记 p=p_{a,d},q=p_{b,c}，我们有 p\le d,q\le c。此时 q 不会出现无意义的情况，所以这个证明不需要 w 满足区间包含单调性。

若 p\le q，使 f_{a,c} 取决策 p，f_{b,d} 取决策 q，不等式变为：

f_{a-1,p}+w(p,d)+f_{b-1,q}+w(q,c)\ge f_{a-1,p}+w(p,c)+f_{b-1,q}+w(q,d)

消去相同的 f 项。此时 p\le q\le c\le d，根据 w 满足四边形不等式，这种情况得证。

若 q<p，使 f_{a,c} 取决策 q，f_{b,d} 取决策 p，不等式变为：

f_{a-1,p}+w(p,d)+f_{b-1,q}+w(q,c)\ge f_{a-1,q}+w(q,c)+f_{b-1,p}+w(p,d)

消去相同的 w 项。此时 a-1\le b-1，q<p，根据归纳假设，这种情况得证。

所以，对于这个方程，两维都有决策单调性。

算法一

类似第二类 dp 的算法，从 p_{i-1,j} 到 p_{i,j+1} 枚举决策，此时 j 需要从 n 到 1 枚举。由于两维不同阶，时间复杂度略有不同：

\begin{aligned}&\sum_{2\le i\le m,1\le j<n}p_{i,j+1}-p_{i-1,j}\\=&\sum_{2\le i\le m,2\le j\le n}p_{i,j}-\sum_{1\le i<m,1\le j<n}p_{i,j}\\\le&\sum_{2\le i\le m}p_{i,n}+\sum_{2\le j<n}p_{m,j}\\=&\mathcal O(n(n+m))\end{aligned}

算法二：分治

这个算法适用于所有满足决策单调的情况，不要求 w 满足四边形不等式。

枚举 i，对于每个 i 进行分治：solve(l,r,L,R) 表示要求出 [l,r] 内的 dp 值，这段区间的决策点都只可能在 [L,R] 内。在 [L,R] 内枚举求出 \text{mid} 的 dp 值和决策点位置 M，递归 solve(l,mid-1,L,M),solve(mid+1,r,M,R)。

solve 每次调用需要花 \mathcal O(R-L) 的时间，递归有 \mathcal O(\log n) 层，每层的 R-L 和都为 \mathcal O(n)，所以整个算法总时间复杂度为 \mathcal O(nm\log n)。

算法二的一个 trick

对于有些题目，求某个 w(l,r) 的复杂度并不为 \mathcal O(1)。此时，如果使用分治做法，则可以用类似于莫队的方法移动左右端点，复杂度仍有保证。具体来说，在全局开两个变量 l_0,r_0，以及其他需要的数据结构（比如桶），表示当前数据结构内维护的是 [l_0,r_0] 的信息。实现函数 int w(int l,int r);，里面直接用类似莫队的方法，将 [l_0,r_0] 移动至 [l,r]，维护数据结构，移动完直接查询答案，这样只会有 \mathcal O(nm\log n) 次移动端点和 \mathcal O(nm\log n) 次查询答案。

查询答案次数是显然的，下面证明端点移动次数。在一次 solve 的函数调用里，第一次关于 w 的查询是 w(L,\text{mid})，我们不妨假设在进入这次调用之前，[l_0,r_0] 已经移动到这个区间。这样，一次调用对于端点移动次数的贡献就是，它本身求 \text{mid} 的 dp 值时多次查询之间的移动，和它自己查询完后，将 [l_0,r_0] 移动到两个子问题需要的区间上的移动。对于前半部分，因为需要的 w 右端点固定，只有左端点从 L 移动到 R，所以复杂度可以接受；对于后半部分，在当前的 solve 回溯之前，l_0 都在 [L,R] 内，r_0 都在 [l,r] 内，无论怎么移都不会移出这个范围，所以对于这两次移动，复杂度最多为 2(R-L+r-l)，可以接受。

算法三：wqs 二分

这类 dp 实际上含义为将长度为 j 的序列划分为 i 段，权值和最小。这个含义和 dp 式子可能有细节差异，但是不影响，以下不考虑。

有定理：若 w 满足四边形不等式，则 f_{i,j} 关于 i 下凸。

证明：

考虑证明 f_{i-1,j}+f_{i+1,j}\ge2f_{i,j}，思路是从 f_{i-1,j} 和 f_{i+1,j} 的最优方案在权值不增的条件下调整出两个 f_{i,j} 的可行方案。

设 f_{i-1,j} 的划分方式为 [a_0+1,a_1],[a_1+1,a_2],\cdots,[a_{i-2}+1,a_{i-1}] 其中 a_0=0,a_{i-1}=j；f_{i+1,j} 的划分方式为 b_0\sim b_{i+1}，含义同理。

若存在 x,y 满足 a_x=b_y，则根据 f 的决策单调性，y-x\in\{0,1,2\}。考虑划分方案中 a_x 的左右两侧，若 y-x=0 或 2，则可以去除段数相等的一侧，对另一侧运用归纳；若 y-x=1，则可以交换两种方案的左侧，得到两个段数均为 i 的方案。

否则，根据 f 的决策单调性，一定存在 x 满足 a_{x-1}+1\le b_x+1\le b_{x+1}\le a_x。记这四个位置为 a,b,c,d，因为 w 有四边形不等式，所以 w_{a,d}+w_{b,c}\ge w_{a,c}+w_{b,d}。我们将 f_{i-1,j} 的方案中 [a_{x-1}+1,a_x] 换成 [a,c]，后面的划分方案改为 b_{x+1}\sim b_{i+1}；f_{i+1,j} 的方案中 [b_x+1,b_{x+1}] 换成 [b,d]，后面改为 a_{x}\sim a_{i-1}。调整后的两个方案划分数量都为 i，并且总权值不增，于是得证。

根据凸性，我们可以使用 wqs 二分，check 时使用第一类 dp 的算法即可，时间复杂度 \mathcal O(n\log V)，其中 V 是与值域相关的一个数。

此外，所有第一类 dp 的算法在这里都适用。