0.5*8 边形 != 式

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 离线决策单调性：

\[f_j=\min\limits_{1\leq k<j}g_k+w_{k,j} \]

构造矩阵 \(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 半在线决策单调性：

\[f_j=\min\limits_{1\leq k<j}f_k+w_{k,j} \]

仍然假设 \(w\) 满足四边形不等式。我们无法如离线情况那样直接分治，因为每行的最小值依赖于前面行的最小值。考虑外层 cdq 分治被动转移，分治过程中会确定 \(1\sim x\) 这些列上的元素。

另一种做法是二分栈，每次加入一列，考虑每行在 \(1\sim x\) 列中的最小值位置，则当前加入的列会覆盖掉行的一段后缀（考察二阶混合差分），二分栈维护。复杂度分析同 ODT。

凸性

记满足四边形不等式的矩阵为蒙日矩阵。

蒙日矩阵的 \(k\) 次幂每个位置关于 \(k\) 凸。

这告诉我们：满足四边形不等式的序列划分问题关于段数是凸的。