决策单调性 dp

重修！

upd on 09/14/24：狗屁模拟赛督促我来更新这篇博。

以下讨论最小化问题。

对于 \(n\times n\) 的矩阵，有：

• 子矩阵 \(A_{[i_1,i_2,..,i_k][j_1,j_2,..,j_\ell]}\) 为矩阵 \(A\) 取出 \(i_1,i_2,..,i_k\) 行和 \(j_1,j_2,..,j_\ell\) 组成的矩阵。其中当序列 \(i,j\) 元素连续时为连续子矩阵。
• 行最小值位置 \(\min_i(A)\) 为最大的整数 \(k\) 满足 \(A_{i,k}=\min\limits_{1\le j\le m}A_{i,j}\)。
• 若 \(\forall 1\le i<j\le n,\min_i(A)\le \min_j(A)\)，则 \(A\) 为单调矩阵。
• 若对于 \(A\) 的所有子矩阵 \(A'\)，都满足 \(\forall 1\le i<j\le n,\min_i(A')\le \min_j(A')\)，则 \(A\) 为完全单调矩阵。

容易发现，转移矩阵为单调矩阵时 dp 满足决策单调性。

• 若 \(\forall1\le i_1<i_2\le n，1\le j_1<j_2\le n\)，都有 \(A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1}\)，则 \(A\) 为蒙日矩阵，其中蒙日矩阵为完全单调矩阵。
• 若 \(A\) 满足四边形不等式，则有 \(\forall1\le i<n，1\le j<n\)，都有 \(A_{i,j}+A_{i+1,j+1}\le A_{i,j+1}+A_{i+1,j}\)。

满足四边形不等式的矩阵都是蒙日矩阵，因为上面定义中的限制等于 \(A\) 的二维差分矩阵 \(\Delta A\) 元素 \(\ge 0\)，所以只要针对单独元素的判断就是充要的。

常见的蒙日矩阵有：

• 根据四边形不等式，\(\Delta A_{x,y}\ge 0\)。
• \(A_{x,y}=|x-y|^p,p\ge 1\)。
• \(A_{x,y}=f(x,y)\)，其中 \(f(x)\) 下凸。

离线决策单调性

分治

令 \(solve(l,r,L,R)\) 表示在处理 \(f_{l,..,r}\) 的决策，取值为 \([L,R]\)，每次取出 \(mid\)，找到决策点并继续递归。单次分治复杂度为 \(\mathcal O(n\log N)\)，其中 \(N\) 为决策点值域。

\(^\dagger\)：当 \(A_{x,y}\) 无法快速计算，但是能快速由 \(A_{x,y}\) 推到 \(A_{x+1,y}\) 和 \(A_{x, y+1}\)，在分治中类似莫队的移动指针复杂度也是正确的，因为每层最多移动 \(\mathcal O(N)\) 次。

路径交错原理

发现对于 2D dp 的 \(m\) 个转移矩阵 \(A_1,A_2,\cdots,A_m\)，如果满足决策单调性，则有 \(\min_j(A_{i-1})\le \min_j(A_i)\le \min_{j+1}(A_i)\)，此时我们每层倒着 dp，决策点枚举总时间复杂度为 \(\mathcal O(n^2)\) 的。

在线决策单调性

二分队列

记录三元组 \((x,l,r)\)，表示决策 \(x\) 目前对 \(f_{l,..,r}\) 有贡献。每次加入先把没用的弹掉，然后二分 \([l,r]\) 中从 \(x\) 更优变成 \(i\) 更优的转折点，改一下加进去。

\(^\dagger\)二分栈

\(^\dagger\)：这不算决策单调性，但是与二分队列处理方式类似，便一起记录。

如果对于决策 \(1\le i<j\le n\)，存在分界点 \(p_{i,j}\)，使得在 \([j,p]\) 决策 \(j\) 更优，而 \((p,n]\) 决策 \(i\) 更优，则可以用二分栈优化。

维护当前 \(f_i\) 决策的栈，对于栈顶和次栈顶两个元素 \(t_1,t_2\)，若有 \(p_{t_1,t_2}<p_{t2,i}\)，说明 \(t_2\) 是冗余的，全部扔掉。最后把栈顶 $p_{t_1,t_2}\le i $ 的也扔掉，转移，把决策 \(i\) 扔进去。

剩下一些理论的东西有空再更吧。

https://www.cnblogs.com/AFewSuns/p/quadrangle-inequality.html