Min-Max 容斥学习笔记

有些时候，我们想要计算一个集合 $S$ 里元素的最小值/最大值，设最小值为 $\operatorname{MIN}(S)=\min\limits_{x\in S}x$，最大值为 $\operatorname{MAX}(S)=\max\limits_{x\in S}x$。

但是有时我们想要求 $\operatorname{MIN}(S)$，但却很难求，反而 $\operatorname{MAX}(S)$ 很好求；或者想要求 $\operatorname{MAX}(S)$，但却很难求，反而 $\operatorname{MIN}(S)$ 很好求。那么这时就可以通过 Min-Max 容斥来实现 $\operatorname{MIN}(S)$ 和 $\operatorname{MAX}(S)$ 的互相转化，从而求得 $\operatorname{MIN}(S)$ 或者 $\operatorname{MAX}(S)$。

朴素 Min-Max 容斥

Min-Max 容斥，先给出式子：

$\operatorname{MIN}(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\operatorname{MAX}(T)\\ \operatorname{MAX}(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\operatorname{MIN}(T)\\$

先考虑第一个式子的证明：

首先假设 $S$ 内元素互不相同（离散化），然后令 $S$ 中元素升序排列后的数列为 $A$。

令 $\operatorname{MAX}(T)=A_i$，有以下两种情况：

• $i=1$，那么显然 $|T|=1$，此时 $\operatorname{MAX}(T)=\operatorname{MIN}(S)$，$T$ 的贡献也就是 $(-1)^2\operatorname{MIN}(S)=\operatorname{MIN}(S)$；

• $i>1$，那么集合内显然不可能存在满足 $j>i$ 的 $A_{j}$，那么只有 $2^{i-1}$ 个集合贡献为 $A_i$，显然有 $2^{i-2}$ 个集合的大小是奇数，$2^{i-2}$ 个集合的大小是偶数，它们抵消了，所以此时 $T$ 的贡献是 $0$；

第二个式子证明过程大体相同，只不过 $A$ 换成了降序排列。

Min-Max 的优点在于它能实现 $f(\operatorname{MIN}(S))$ 和 $f(\operatorname{MAX}(S))$ 的不涉及到取 $\min$ 和取 $\max$ 操作的互相转化，其中 $f$ 是任意一个线性函数，例如期望。

理解了它的原理后也不难推出式子：

$f(\operatorname{MIN}(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}f(\operatorname{MAX}(T))\\ f(\operatorname{MAX}(S))=\sum\limits_{T\subseteq S}(-1)^{|T|+1}f(\operatorname{MIN}(T))\\$

Kth-Min-Max 容斥

Min-Max 容斥的另一个优点在于，它还能求出集合 $S$ 的第 $k$ 大/小 $\operatorname{MAX}_k(S)$ 和 $\operatorname{MIN}_k(S)$，推导如下：

考虑令 $\operatorname{MIN}_k(S)=\sum\limits_{T\subseteq S}F(|T|)\operatorname{MAX}(T)$，构造 $F$。

类似的，假设 $S$ 内元素互不相同（离散化），然后令 $S$ 中元素降升序排列后的数列 $A$。

我们设 $\operatorname{MAX}(T)=A_p$ 那么显然只有 $T$ 不包含满足 $j>p$ 的 $A_j$ 才能让 $\operatorname{MAX}(T)=A_p$，即有 $p-1$ 个数可供选择，所以对于所有满足 $\operatorname{MAX}(T)=A_p$ 的 $T$，它的系数 $F$ 是：

$\sum\limits_{i=0}^{p-1}\dbinom{p-1}{i}F(i+1)$

求和函数的变量 $i$ 表示除了 $A_p$ 外多选的元素，然后 $F(i+1)$ 表示选那么多数的贡献系数，$\dbinom{p-1}{i}$ 表示可以随便选择。

然后我们想让 $F$ 满足：

$\sum\limits_{i=0}^{p-1}\dbinom{p-1}{i}F(i+1)=[p=k]$

即：

$\sum\limits_{i=0}^{p}\dbinom{p}{i}F(i+1)=[p=k-1]$

二项式反演一下：

$[p=k+1]=\sum\limits_{i=0}^{p}\dbinom{p}{i}F(i+1)\Rightarrow F(p+1)=\sum\limits_{i=0}^{p}(-1)^{p-i}\dbinom{p}{i}[i=k-1]$

即：

$F(p)=(-1)^{p-k}\dbinom{p-1}{k-1}$

所以：

$\operatorname{MIN}_k(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\operatorname{MAX}(T)\\ \operatorname{MAX}_k(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-1}{k-1}\operatorname{MIN}(T)$

代入 $k=1$ 验证：

$\begin{aligned} \operatorname{MIN}_1(S)&=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\dbinom{|T|-1}{1-1}\operatorname{MAX}(T)\\ &=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\operatorname{MAX}(T)\\ \end{aligned}$

发现得到了之前的式子，所以我们推对了。

同样的，Kth-Min-Max 容斥也可以套上任意线性函数。

应用

HDU 4624 Endless Spin

双倍经验：ABC242Ex Random Painting

要求所有球均被染色的时间，可以通过 Min-Max 容斥转化为求一个子集 $S$ 中的球最早被染色的时间 $Tme_S$。

进一步的，若 $S$ 中的球被染色的概率为 $p$，那么 $Tme_S$ 就等于 $\frac{1}{p}$。

而被染色的概率很好求，只要求出能给这些球染色的区间个数 $sum$，除以总的区间个数 $\binom{n}{2}+n$ 即可。

那么直接设 $dp_{i,j}$ 表示前 $i$ 个球处理完毕，当前子集 $S$ 选了球 $i$ 且不被染色的选区间的方案数为 $j$ 的选子集的方案数，转移的时候把容斥系数也乘进去，最后套 Min-Max 的式子即可。

时间复杂度 $O(n^4)$。