闵可夫斯基和 学习笔记

什么是闵可夫斯基和？

在几何上，给定两个点集 $A$ 和 $B$，它们的闵可夫斯基和定义为： $$C = A + B = \{ a + b \mid a \in A, b \in B \}$$ 也就是把 $A$ 中的每一个点和 $B$ 中的每一个点做向量加法。

【结论】
如果 $A$ 和 $B$ 都是凸多边形，那么它们的闵可夫斯基和 $C$ 也是一个凸多边形。
更绝的是，$C$ 的边集，恰好是 $A$ 的边集和 $B$ 的边集按照极角排序后拼接在一起的结果！

例如：对于点集 $P=\{(0,0),(-3,3),(2,1)\}$ 和 点集 $Q=\{(0,0),(-1,3),(1,4),(2,2)\}$，

将 $P$ 沿 $Q$ 的每个向量平移：

不难发现新图形也是一个凸包：

而新图形的边正是 $P$ 的边和 $Q$ 的边按照极角排序后拼接在一起得到的。

【例题】[JSOI2018] 战争

转化：有交 $\iff \exists a\in A, b\in B,\ a+\vec{v}=b \iff \vec{v} = b - a \in B + (-A)$。
解法：求出 $B$ 与 $-A$ 的闵可夫斯基和 $C$（凸多边形），问题变为判断点 $\vec{v}$ 是否在 $C$ 内。复杂度 $O((n+m+q)\log n)$。

【例题】[USACO22JAN] Multiple Choice Test P

转化：目标是最大化向量和的模长。模长函数是凸函数，最大值必然在可能和的凸包的顶点上取得。而可能和的集合正是所有组向量集合的闵可夫斯基和。因此，我们只需要计算所有组向量的闵可夫斯基和的凸包，再遍历顶点取最大距离。
解法：对每组向量求凸包，提取边向量（相邻顶点之差），将所有边向量按极角排序，然后从起点开始依次相加，得到闵可夫斯基和凸包的所有顶点，最后计算每个顶点到原点的平方距离，取最大值。复杂度 $O(T\log T)$（$T$ 为总向量数）。

回到 DP：它和优化有什么关系？

在算法竞赛中，我们遇到的通常不是二维平面上的乱斗，而是关于序列的 DP 状态合并。

最经典的场景就是树上背包：

$$h(k) = \max_{i+j=k} (f(i) + g(j))$$

这叫作 $(\max, +)$ 卷积。通常它的复杂度是 $O(|f| \times |g|)$ 的。

【结论】
如果 $f$ 和 $g$ 都是上凸函数（即差分单调递减，$\Delta f(i) = f(i+1) - f(i)$ 单调递减），把 $f$ 和 $g$ 的图像看作二维平面上的上凸壳，那么 $h$ 的图像恰好就是 $f$ 和 $g$ 的闵可夫斯基和的上边界！

既然凸多边形的闵可夫斯基和只是把边按斜率（极角）排序，而在 1D 函数中，边就是差分，斜率就是差分的值，那么计算 $h$ 的差分数组 $\Delta h$，只需要将 $\Delta f$ 和 $\Delta g$ 这两个单调递减的数组，像归并排序一样合并起来即可！

复杂度发生了质变：从 $O(|f| \times |g|)$ 降到了 $O(|f| + |g|)$。

【例题】[ICPC 2022 Nanjing R] 工厂重现

DP 结构：定义 $f_u(j)$ 为以 $u$ 为根的子树内选 $j$ 个工厂，且所有工厂到 $u$ 的加权距离和等辅助信息下的最大贡献。转移是 $(\max,+)$ 卷积合并各子树。
优化：$f_u$ 是上凸函数，其差分数组单调递减。合并子树等价于对差分数组做闵可夫斯基和（归并）。用平衡树维护差分序列，启发式合并，并支持因连边产生的区间加等差数列的标记。复杂度 $O(n\log^2 n)$。

【例题】[APIO 2016] 烟花表演

DP 形式：设 $f_u(x)$ 为使 $u$ 子树内所有叶子到 $u$ 的距离均为 $x$ 的最小代价。转移包含 $(\min,+)$ 卷积：$f_u(x) = \sum_{v} \min_{y} \{ f_v(y) + |w_{uv} + y - x| \}$，并叠加绝对值函数。$f_u$ 均为下凸函数。
与闵可夫斯基和的联系：下凸函数的 $(\min,+)$ 卷积等价于对其斜率（差分）做闵可夫斯基和。因此转移的本质是合并多个下凸壳的边序列。
实现：利用 Slope Trick，用可并堆（左偏树）维护拐点，以此表示斜率的变化。合并堆即为闵可夫斯基和，插入/删除拐点对应添加绝对值函数等操作。复杂度 $O(n\log n)$。

【例题】[THUPC 2024 初赛] 一棵树：

DP 结构：令 $dp_{u,i}$ 表示以 $u$ 为根的子树内选 $i$ 个黑点的最小权值。转移时合并子节点： $$dp_{u,i} = \min_{j} \{ dp_{v,j} + |k - 2j| + dp_{u,i-j} \}.$$ 设 $f_{v,j} = dp_{v,j} + |k - 2j|$，则转移变为 $(\min,+)$ 卷积 $dp_u = f_v \oplus dp_u$。
优化：归纳可证 $f_v, dp_u$ 均为下凸函数，差分数组单调递增。$(\min,+)$ 卷积等价于对差分数组做闵可夫斯基和（归并）。$\Delta f_v$ 由 $\Delta dp_v$ 经前缀 $-2$、后缀 $+2$ 得到（奇偶性略有不同）。用堆维护前 $\lfloor k/2 \rfloor$ 个差分，vector 维护剩余部分，合并时启发式合并，打标记处理区间加减。复杂度 $O(n\log^2 n)$。