Min-Max Inclusion Exclusion Principle

Preface

Min-Max容斥是一种反演，\(\text{aka}\) 最值反演，适用于一种最值已知或者相对容易求得的情况下求另一最值的问题。

Content

Introduction

令全集 \(U=\{a_1,a_2,a_3,\dots,a_n\}\)，令 \(\min(S)=\min\limits_{a_i\in S}a_i\)，\(\max(S)=\max\limits_{a_i\in S}a_i\)；不妨假设我们可以轻易求 \(\min(S)\)，但 \(\max(S)\) 不易求，有结论：

\[\max(S)=\sum\limits_{T\subseteqq S}(-1)^{|T|+1}\min(T) \]

注意，我们认定 \(a_i\ne a_j\)，当且仅当 \(i\ne j\)，认定 \(T_1\ne T_2\) 当且仅当 \(\exists i,a_i\in T_1 \land a_i\notin T_2\)；

证明：令 \(U\) 单调递增且 \(|U|=k\)，有 \(\min(U)=A_1\)：

\(k=1\)

\(U=\{A_1\}\)

\(\max(U)=\min(U)=A_1=(-1)^2A_1\)
\(k>1\)
- \(A_1=\min(S)\) 即 \(A_1\in S\) 共 \(2^{k-1}\) 种，有 \(2^{k-2}\) 种 \(|S|\equiv1\pmod2\)，有 \(2^{k-2}\) 种 \(|S|\equiv0\pmod2\)，正负相消。
- \(A_2=\min(S)\) 即 \(A_2\in S \land A_1 \notin S\) 共 \(2^{k-2}\) 种，有 \(2^{k-3}\) 种 \(|S|\equiv1\pmod2\)，有 \(2^{k-3}\) 种 \(|S|\equiv0\pmod2\)，正负相消。
- \(\dots\)
- \(A_k=\min(S)\) 即 \(A_k\in S \land A_{[1,k)} \notin S\) 共 \(1\) 种，且贡献为 \((-1)^2A_k\).