凸性 DP 优化

首先这里点名 \(\rm WQS\) 二分还有决策单调性，但是今天就不写这个了，今天学了一些进阶的东西。

闵可夫斯基和

这个东西时是用来优化一类凸函数卷积的，一般就是背包或者分治时使用。最常用的是 \((\max / \min, +)\) 卷积。

首先考虑这个卷积式：\(f_k = \max_{i + j = k} \{ g_i + h_j \}\)，暴力做卷积是 \(O(n^ 2)\) 的。

其中 \(g, h\) 具有凸性时，有以下性质：

性质 \(1\). \(f\) 也具有凸性。

考虑卷积的组合意义，假设我们将 \(g, h\) 分别差分得到 \(\Delta g, \Delta h\)，每个数看做有相应价值的物品。那么 \(f_k\) 就相当于在两个数组中选出 \(k\) 个物品，且满足在 \(\Delta g, \Delta h\) 中都是一个前缀。但由于具有凸性，\(\Delta g, \Delta h\) 都是单调下降的，因此每次选的物品的价值都是单调下降的，即 \(\Delta f\) 是单调下降的。因此 \(f\) 具有凸性。这进一步给出了性质二。

性质 \(2\). \(\Delta f\) 与 \(\Delta g, \Delta h\) 排序后一样

首先把 \(\Delta g, \Delta h\) 排序后得到一个数组 \(a\)，因为 \(g, h\) 都有凸性，因此不难发现 \(a\) 中的某一个前缀都对应着 \(\Delta g, \Delta h\) 中的两个前缀的并集。因此，对于 \(f_i\)，直接取 \(a\) 中最大的前 \(i\) 个数是合法的。同时，这个也是答案上界。

因此，我们有了第二个性质后，不难通过归并排序直接直接做到 \(O(n)\) 卷出 \(f\)。这个被我们成为闵可夫斯基和。