写在前面：文章中 ${\max}_k(S)$ 表示集合 $S$ 中第 $k$ 大的元素，${\min}_k(S)$ 同理，$k=1$ 时会省略下标 $k$ 。

---

 

Min-max容斥是一种通过集合中的元素表示出集合第 $k$ 大（小）元素的容斥，往往在比较元素大小较难时使用。

既然要将集合第 $k$ 大表示成容斥形式，于是我们可以设出一个这样的式子：

$${\max}_k(S)=\sum\limits_{\varnothing\not=T\subseteq S}{a_{|T|}\min(T)}$$

考虑分开对集合中每一个数算贡献，每个数只有和他在同一个集合的数全比他大才会产生贡献，答案即为：
$${\max}_k(S)=\sum\limits_{i=1}^{|S|}{\max}_i(S) \sum\limits_{j=1}^{i}a_j\dbinom{i-1}{j-1}$$

而显然：

$${\max}_k(S)=\sum\limits_{i=1}^{|S|}{\max}_i(S)[i=k]$$

所以可以得出：

$$\sum\limits_{j=1}^{i}a_j\dbinom{i-1}{j-1}=[i=k]$$

设 $g(i)=[i=k]$，可以转化为：

$$g(i)=\sum\limits_{j=1}^{i}a_j\dbinom{i-1}{j-1}$$

$$g(i)=\sum\limits_{j=0}^{i-1}a_{j+1}\dbinom{i-1}{j}$$

发现这个式子可以二项式反演，但是发现形式不大符合，考虑进行转换：

设 $h(i-1)=g(i),\ b_j=a_{j+1}$，得到：

$$h(i-1)=\sum\limits_{j=0}^{i-1}b_j\dbinom{i-1}{j}$$

这个式子大可二项式反演，得到：

$$b_{i-1}=\sum\limits_{j=0}^{i-1}h(j)\dbinom{i-1}{j}(-1)^{i-1-j}$$

将 $g$ 和 $a$ 带回去：

$$a_{i}=\sum\limits_{j=0}^{i-1}g(j+1)\dbinom{i-1}{j}(-1)^{i-1-j}$$

发现只有当 $j+1=k$ 时 $g$ 才不为 $0$，所以：

$$a_i=\dbinom{i-1}{k-1}(-1)^{i-k}$$

于是就得出了Min-max容斥的式子了：

$${\max}_k(S)=\sum\limits_{\varnothing\not=T\subseteq S}{\dbinom{|T|-1}{k-1}(-1)^{|T|-k}\min(T)}$$

注意：若 $|T|-1<k-1$，贡献就是 $0$。

同样，${\min}_k(S)$ 的表示也同理，只需要把 $\min$ 和 $\max$ 交换一下就好了。

值得一提的是，这个式子在期望意义下同样适用：

$$E({\max}_k(S))=\sum\limits_{\varnothing\not=T\subseteq S}{\dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(\min(T))}$$