昨天为了一道最小割树去看了 16 年王文涛的集训队论文，今天刚刚翻看了上场 ABC_Ex 的题解，连续两次碰见了 submodularity 这个词，简单记记自己的理解。其实只是想整理下思路，收集一下看不懂的博客。以下内容随意且不严谨。
submodularity 次模性或者叫子模性是运筹学中的重要概念，它描述了一个集合函数“边际效用递减/递增”的情况。对于定义在集合 \(U\) 子集上的函数 \(f\)，我们定义 \(S\) 对于一个 \(e\notin S\) 的边际效用为 \(\Delta(e|S)=f(S\cup\{e\})-f(S)\)。那么边际效用递减就是指对于 \(T\subset S\) 有 \(\forall e\notin S,\Delta(e|S)\leq \Delta(e|T)\)。经过简单的推导，我们根据边集效用的单调性可以导出次模性的式子：\(f(A\cup B)+f(A\cap B)\leq f(A)+f(B)\)。上一次碰见这个式子是在 pb 博客 讲拟阵中的秩函数满足次模性（虽然那篇博客我现在都没看懂就是了）。
发现什么了吗？四边形不等式，或者叫做蒙日性，同样描述了一个定义在区间上的边际效用的单调性！回想我老早之前写的博客 里就讲了如何利用一个边际效用递减证明四边形不等式，以及使用了四边形不等式证明了区间划分类 DP 的决策单调性。
后来，我做了序列变换这道题，我这样理解：四边形不等式是一种二维的凸性，所以 \((\min,+)\) 矩阵乘法和一维的 \((\min,+)\) 卷积一样。一维凸性 \(\to\) 闽可夫斯基和，二维凸性（四边形不等式） \(\to\) 更快的广义矩阵乘法！
再后来，看到 ix35 的这篇博客，我终于了解到这种“更快的矩阵乘法”叫做蒙日矩阵乘法。这就是为什么四边形不等式也叫 Mongeness，而且还有更多比蒙日矩阵性质更好的矩阵，可以算更快的蒙日矩阵乘法，然而到现在 ix35 的这篇博客内容我一个字都看不懂！
有一天，我看到了这篇Itst 的博客，证明了区间划分类 DP 如果满足四边形不等式就满足答案凸性！
这样说来，四边不等式是一种二维的凸性，次模性可以看成定义在幂集上的一个凸性，而凸性是 DP 优化的利器，有了这些性质我们就可以扣开决策单调性/凸性优化 DP 的大门。
到了昨天，我知道了带权无向图的割函数 \(c(S)\) 满足次模性，甚至还满足一个叫做 posi-modular 的性质。根据这两个性质我们可以证明任意两点间可能的最小割存在一种构造使其形成一个集合包含的树形结构。这样我们就可以缩点+分治+维护划分构造出来一种能够构造解的正统 Gomory-Hu Tree。
今天看到这道 ABC 的 Ex，感慨万千，前面论述了为什么这道题满足四边形不等式，甚至于满足次模性。这道题让我们处理的就是区间划分类 DP，所以答案关于段数的函数 \(d\) 有凸性！后面指出了一个三个 \(\log\) 的做法：直接利用 \(d\) 的单调性二分外层，内层 wqs 二分利用了四边形不等式带来的 \(d\) 的凸性，而由于内层 DP 性质比较少，我们考虑直接忽略 cost 比 \(X\) 大的区间，这样需要考虑的区间个数就是 \(n\log X\) 级别的了，可以用一个 \(n\log X\) 计算 DP。
然而最外层的那个关于单调性的二分太冗余了，内外层两个二分都是在处理 \(d\) 函数，太浪费了！于是题解给出了一种改造式的 wqs 二分一次干完了两个工作。
回顾我关于信息学中凸性的认识过程，感叹有太多本质深奥的内容我不知道了，信息学术还有很多内容等待着我们去探索。而且这种探索不应该只为了 OI，仅限于 OI。
在这里随感个什么劲呢，Ex 代码都不写
代码咕了