Itst，神。感觉四边形不等式方面的理论学这么多就够了。
子矩阵指选出若干行和若干列，行列交点构成的矩阵；连续子矩阵指选取的行连续且列连续的子矩阵。
四边形不等式
对于矩阵 \(A\)，若对于 \(1\leq i_1\leq i_2\leq n\)，\(1\leq j_1\leq j_2\leq m\)，\(A_{i_2,j_2}+A_{i_1,j_1}\leq A_{i_1,j_2}+A_{i_2,j_1}\)，则称 \(A\) 满足四边形不等式。
将式子做变形，得到 \(A_{i_2,j_2}-A_{i_1,j_2}-A_{i_2,j_1}+A_{i_1,j_1}\leq 0\)，这同我们熟知的二阶混合差分形式类似，容易发现 \(A\) 满足四边形不等式等价于 \(A\) 的二阶混合差分在除了第一行、第一列处均非正。因此可以 \(O(nm)\) 判定四边形不等式。
单调矩阵
记 \(\min_i(A)\) 代表 \(A\) 第 \(i\) 行最后一个最小值的位置，若 \(\min_i(A)\) 不降，称为单调矩阵。每个子矩阵都单调的矩阵称作完全单调矩阵。
Lemma1：若 \(A\) 满足四边形不等式，则 \(A\) 和 \(A^T\) 均完全单调。
直接从 \(A\) 的二阶混合差分矩阵出发考虑容易证明。
Lemma2：若 \(A\) 满足四边形不等式，则将 \(A\) 的一列或一行加上常数 \(c\)，所得矩阵仍然满足四边形不等式。
从四边形不等式的定义式出发容易证明。
离线决策单调性
考虑 1D-1D 离线决策单调性：
构造矩阵 \(A\)：
- \(x>y\)，\(A_{x,y}=g_y+w_{x,y}\)
- \(x\leq y\)，\(A_{x,y}=+\infty\)
容易发现 \(f_j=\min_j(A)\)，即需要对矩阵 \(A\) 求出每行最小值的位置。当 \(w\) 满足四边形不等式时，\(A\) 也满足四边形不等式。
一点小问题
对 \(w\) 检查四边形不等式时只需要对所有主对角线下方的位置检查，原因是当主对角线下方满足四边形不等式时，可以构造出其余位置使得其值极大且满足四边形不等式。
我们要对一个完全单调矩阵求出每行最小值所在的位置。直接分治求解可以做到 \(O(m\log n)\)。当矩阵每个位置贡献难算，且不同位置之间增量易算时，考虑分治过程中每层会将行分成若干个连续段，每段会有一个列的连续段代表最小值的位置范围，同时这个位置范围关于行是单调的，容易通过计算位置之间增量来进行分治。
半在线决策单调性
考虑 1D-1D 半在线决策单调性：
仍然假设 \(w\) 满足四边形不等式。我们无法如离线情况那样直接分治，因为每行的最小值依赖于前面行的最小值。考虑外层 cdq 分治被动转移，分治过程中会确定 \(1\sim x\) 这些列上的元素。
另一种做法是二分栈，每次加入一列，考虑每行在 \(1\sim x\) 列中的最小值位置，则当前加入的列会覆盖掉行的一段后缀（考察二阶混合差分），二分栈维护。复杂度分析同 ODT。
凸性
记满足四边形不等式的矩阵为蒙日矩阵。
蒙日矩阵的 \(k\) 次幂每个位置关于 \(k\) 凸。
这告诉我们：满足四边形不等式的序列划分问题关于段数是凸的。