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\) 凸。
这告诉我们:满足四边形不等式的序列划分问题关于段数是凸的。