一个逆天的容斥。
形式非常简单：
\[\max_{i\in S}i=\sum_{T\subseteq S}(-1)^{|T|+1}\min_{i\in T}i \]其中 \(S\) 是你要求最大值的集合。
这个东西有什么用呢？显然一般题是完全不需要这个逆天玩意的。
但是这个容斥对于期望成立。所以一些形似求覆盖的期望用时的题就需要用到这个东西。
例题：P3175
这个东西就是一眼 Min-Max 容斥。因为他要求期望所有位都变成 \(1\) 的时间，而这个时间看的是最晚变成 \(1\) 的一位变成 \(1\) 的期望，也就是最大值。加上奇怪的求期望，显然只能 Min-Max。
设 \(f_S\) 表示 \(S\) 中至少有一位被覆盖的最小期望时间，形式化地，就是 \(f_S = \min_{i\in S}E(t_i)\)，其中 \(E(t_i)\) 就是第 \(i\) 位被覆盖的期望时间。
那么显然答案就是 \(\sum_{T\subseteq S}(-1)^{|T|+1}f_T\)，而 \(f_T\) 的求法也相当简单，只需看与 \(T\) 有交集的所有数的选中概率 \(p\)，然后 \(f_T = \frac{1}{p}\)。求 \(p\) 可以转成所有与 \(T\) 不交的概率之和，也就是 \(T\) 在全集 \(S\) 中的补集的全部子集的概率之和。这可以高维前缀和或 FWT 解决。
依旧是一眼 Min-Max 容斥。设 \(g_i\) 表示恰好有 \(i\) 个区间覆盖选定位置集合 \(T\) 中至少一个位置的 集合的 \(\sum (-1)^{|T|+1}\)，则显然答案就是 \(\sum_i g_i \times \frac{m}{i}\)。
那么显然 \(n^3\) 的暴力 dp 是显然的。只需设 \(f_{i,j}\) 表示上一个位置选定的是 \(i\)，一共有 \(j\) 个集合覆盖至少一个选定位置的答案，那么只需枚举下一个位置是什么，设 \(l\) 是所有左端点在 \((i,k]\)，右端点在 \([k,INF]\) 的个数，则 \(f_{k,j+l}\leftarrow f_{i,j}\)。
优化的话是把 \(g_i\) 的定义改成没有覆盖任何位置集合中的位置的区间个数为 \(i\) 的答案，设 \(dp_{i,j}\) 就是上一个钦定的是 \(i\)，右端点在 \([1,i]\) 的有 \(j\) 个没有任何覆盖的答案。
然后用线段树维护前面每一个 \(dp_j\) 对当前 \(dp_{i+1}\) 的贡献系数。
那么只需挨个加入每一个右端点是 \(i+1\) 的区间，考虑这个区间 \([j,i+1]\) 对前面 \(k\in [0,j)\) 的所有 \(dp_k\) 都导致了一个右移，于是线段树即可维护。
标签：期望,Min,Max,sum,容斥,dp From： https://www.cnblogs.com/infinities/p/17168126.html