闵可夫斯基和 学习笔记

· · 算法·理论

什么是闵可夫斯基和？

在几何上，给定两个点集 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|)。

【例题】The 2022 ICPC Asia Nanjing Regional Contest Problem H. Factories Once More

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

【例题】[APIO2016] 烟花表演

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)。