min-max容斥
描述
对于一个集合 \(S\) 有
\[ \begin{align} \max(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) \\ \min(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \max(T) \end{align} \]
其中 \(\max(S)\) 表示集合 \(S\) 中的最大元素，\(\min(S)\) 表示 \(S\) 中的最小元素
证明略
在期望下也成立
\[ \begin{align} 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)) \end{align} \]
不会证