学习笔记：Min-Max 容斥

Min-Max 容斥

Min-Max 容斥是一种用于 Min/Max 互相转换的小技巧，通常在与 Min/Max 有关的计数问题中被广泛是使用。

能用 Min-Max 容斥解决的问题一般数据范围相对较小。

设全集为 U=\left\{a_1, a_2, a_3, ……, a_n\right\}，则令：

\max(s) = \max_{a_i \in U}a_i \\ \min(s) = \min_{a_i \in U}a_i

假设这样一种情况：在某一道签到毒瘤题中我们可以很轻松地求出 min(s)，却不会或者很难求出 max(s)。这个时候 Min-Max 容斥就可以提供一种非常巧妙的方式将 min(s) 转换为 max(s)（反过来也是可以的）。

先把结论贴出来：

\max(s)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T)

那么，如何证明这个结论的合理性呢？

首先假设 U 内元素各不相同，不影响结论正确性。

不妨对 U 降序排列，令 A_k 为此时 U 中的第 k 个元素。

令 \min(T)=A_k，考虑进行分类讨论：

当 k=1 时，此时 \min(T)=\max(T)，易知贡献为 (-1)^{1+1}\min(T)=\max(T)。
当 k>1 时，此时 T 只能包含 A_i,i \in [1, k] 中的元素。同时 A_k 已经钦定其在 T 中。剩余的元素有 2^{k-1} 种选法。其中 |T| 为奇数和偶数的情况各占一半，贡献互相抵消。

综上所述，原式成立。

当然这个结论显然是对称的，即：

\max(s)=\sum_{T\subseteq S}(-1)^{|T|+1}\min(T) \\ \min(s)=\sum_{T\subseteq S}(-1)^{|T|+1}\max(T) \\

其在期望意义下的结论为：

E(\max(s))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T)) \\ E(\min(s))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\max(T)) \\