浅谈 mex
a_foolish_OIer
·
·
算法·理论
设 $S$ 是一个可重非负整数集合，则 $\operatorname{mex}(S)$ 表示 $S$ 中最小的未出现过的非负整数。
如 $\operatorname{mex}(\{0,1,3,1,0\})=2$，$\operatorname{mex}(\{1,1,4,5,1,4\})=0$。
$\operatorname{mex}$ 运算有一些广为人知的结论。
### Conclusion 1.1
记 $T=\{x | x \in S\}$，$\operatorname{mex}(S) \le |T|$。
### Conclusion 1.2
若 $S \subseteq T$，则 $\operatorname{mex}(S) \le \operatorname{mex}(T)$。
### Conclusion 1.3
若 $A \in S$，则 $\operatorname{mex}(S) \ne A$。
### Conclusion 2.1
对于一个 $0 \sim n-1$ 的排列 $p$，有 $\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_r\})=\min \limits_{j \notin [l,r]} \{p_j\}$。
::::info[Prove]
由 $\operatorname{mex}$ 的定义知，$\operatorname{mex}$ 等于补集 $\min$，所以就是不在 $[l,r]$ 内的最小值。
::::
::::warning[Special]
对于 $l=1,r=n$ 的情况，$\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_r\})=n$。
::::
### Conclusion 2.2
对于一个 $0 \sim n-1$ 的排列 $p$，$\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_r\})=\min(\operatorname{mex}(\{p_l,p_2,\ldots,p_r\}),\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_n\}))$。
::::info[Prove]
设 $x=\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_r\})$，这等价于 $0 \sim x-1$ 均在 $[l,r]$ 中出现。
考虑数 $x$，剩下的 $[1,l-1]$ 和 $[r+1,n]$ 是不交的，所以其中必然有一部分没有 $x$，又因为 $[1,r]$ 和 $[l,n]$ 都包含 $0 \sim x-1$，所以有 $\min(\operatorname{mex}(\{p_l,p_2,\ldots,p_r\}),\operatorname{mex}(\{p_l,p_{l+1},\ldots,p_n\}))=x$。
::::
### Conclusion 3
记 $i$ 表示一种状态，$\operatorname{mex}(i)$ 表示状态 $i$ 下的题目所求的 $\operatorname{mex}$，有 $\sum \limits_i \operatorname{mex}(i)=\sum \limits_j \sum \limits_{\operatorname{mex}(i) = j} j=\sum \limits_j \sum \limits_{\operatorname{mex}(i) \ge j} 1$。
注意到 $\operatorname{mex} \ge x$ 的充要条件是 $0 \sim x-1$ 都出现在集合中。
这可以简化很多计数的模式。
### Conclusion 4
对于一个序列 $a$，定义一个好区间 $[l,r]$ 满足不存在 $[l_0,r_0]$ 满足 $[l_0,r_0] \subset [l,r]$ 且 $\operatorname{mex}(\{a_l,a_{l+1},\ldots,a_r\})=\operatorname{mex}(\{a_{l_0},a_{l_0+1},\ldots,a_{r_0}\})$，则好区间的数量 $\le 2n$ 个。
::::info[Prove]
设现在有一个区间 $[l,r]$ 的 $\operatorname{mex}$ 不为 $0$，不妨设 $a_l<a_r$，$a_l>a_r$ 同理。
首先 $\operatorname{mex}(\{a_l,a_{l+1},\ldots,a_r\}) \ne a_l$，若 $\operatorname{mex}(\{a_l,a_{l+1},\ldots,a_r\})<a_l$，显然可以把 $a_l$ 扔出去。
设有一个 $r_0>r$ 满足 $[l,r_0]$ 是一个好区间，且 $a_l>a_{r_0}$，然而 $a_{r_0}<a_l<\operatorname{mex}(\{a_l,a_{l+1},\ldots,a_r\})$，这意味着不会产生任何额外的贡献，所以 $[l,r_0]$ 不是一个好区间。
所以我们就证明了，对于每个 $l$，至多有一个 $r$，使得 $a_l>a_r$ 且 $[l,r]$ 是一个好区间。
对于 $\operatorname{mex}=0$ 的情况，只能是 $[i,i]$ 的情况。
我们证明了最多有 $2n$ 个区间是好的。
::::
## Problems
#### CF2057A MEX Table
::::success[Sol]
由结论 1.1 可得，行贡献最多是 $n$，列贡献最多是 $m$，显然 $0,1$ 只能在同一列/行上，贪心得到答案为 $\max(n,m)+1$。
::::
#### P15652 [省选联考 2026] 排列游戏
::::success[Sol]
[推销一下题解](https://www.luogu.com.cn/article/7hgnk2fr)
首先根据结论 2.1，这意味着让所有 $\operatorname{mex}$ 相等，等价于让前后缀 $\min$ 相等即可，我们先用 $2n$ 次查询出 $p$ 的前后缀 $\min$，对于前后缀 $\min$ 产生改变的地方，就把这个值填上去。
对于剩下的，为了不干扰前后缀 $\min$，考虑贪心策略，对于要求 $\min$ 越大的位置匹配越大的数，这肯定能产生一组解。
然后你发现若前后缀 $\min$ 出现了 $0$ 就不用继续询问了，剩下的肯定都是 $0$，然后就把 $2n$ 次变成了 $n$ 次。
::::
#### P13662 「TPOI-5A」Luminescence
::::success[Sol]
由结论 2.1 可得，$[l,r]$ 权值就是 $\min(a_{l-1},b_{r+1})$。
于是所有合法排列权值都相等，可以直接计数。
::::
#### CF2163D2 Diadrash
::::success[Sol]
首先根据结论 1.2，所以对于一个区间，存在另一个区间完全包含当前区间的话是没有意义的，于是最后会留下 $O(n)$ 个。
考虑做一个二分，根据结论 2.2，可以发现只需要通过比较 $\operatorname{mex}(1,r),\operatorname{mex}(l,n)$ 可以得出 $\operatorname{mex}$ 更大的位置。
总共 $2\lceil \log_2 n\rceil=28$ 次。
::::
#### CF1292C Xenon's Attack on the Gangs
::::success[Sol]
依次考虑放入 $0,1,\ldots,n-2$，计算对于 $u,v$ 之间路径的答案。
容易发现肯定是外面的比里面的要大，也就是说是个单谷形式。
记 $g(i)$ 表示 $\sum \limits_{1 \le u,v \le n} [\operatorname{mex}(u,v) \ge i]$，考虑 dp，记 $f_{u,v}$ 表示把 $0∼l−1$ 放在 $u,v$ 之间的路径上的最大贡献，由结论 3 得 $f_{u,v}=\sum g(i)$。
由于是单谷，分类讨论有 $f_{u,v}=\max(f_{u,x},f_{y,v})+s_{u,v} \cdot s_{v,u}$，其中 $x$ 表示 $v$ 的父亲，$y$ 表示 $u$ 在当前情况下的父亲，$s_{r,i}$ 表示以 $r$ 为根 $i$ 的子树大小。
::::
#### CF2030E MEXimize the Score
::::success[Sol]
先求出一个序列的贡献，记 $c_i$ 表示 $i$ 在序列中的出现次数。
贡献为 $\sum d_i \cdot i$，$d_i$ 表示 $\operatorname{mex}=i+1$ 可重集合的个数，$d_i$ 显然可以用 $c_i$ 算出。
但是这样太麻烦了，考虑计算一个数对于整体是否有贡献，将数从小到大考虑，数 $i$ 有贡献当且仅当存在一个可重集合的 $\operatorname{mex}=i$，对于所有的数 $i$，前面至多产生 $\min \limits_{j=0}^{i-1} \{c_j\}$ 个这样的可重集合，所以这个数 $i$ 对于整体的贡献为 $\min \limits_{j=0}^i \{c_j\}$，但是我一开始算的是没有贡献的，把这个展开一下就是 $c_i-\max(0,c_i-\min \limits_{j=0}^{i-1} \{c_j\})$，这一部分同样可以使用结论 3 得出。
然后有一个思路就是计算这个序列的贡献和能在原序列中出现多少次，注意到对于数 $i$，我们只关心 $\min \limits_{j=0}^i \{c_j\}$ 的值，记 $f_{i,j}$ 表示到数 $i$ 为止的前缀 $\min=j$ 的总贡献，为了辅助计算，再令 $g_{i,j}$ 表示表示到数 $i$ 为止的前缀 $\min=j$ 的方案数。
乍一看状态数是 $O(n^2)$ 的，实际上对于 $j$ 这一维，$\max \{\sum j\}=\sum c_i=n$，状态数是 $O(n)$ 的。
边界条件显然为 $g_{0,i}=\begin{pmatrix} c_0 \\ i \end{pmatrix}$，$f_{0,i}=\begin{pmatrix} c_0 \\ i \end{pmatrix} \cdot i$。
暴力转移，枚举 $j$ 表示数 $i$ 取了 $j$ 个，$k$ 表示数 $i-1$ 为止的前缀 $\min$，直接转移有：
- $g_{i,\min(j,k)}=g_{i-1,k} \cdot \begin{pmatrix} c_i \\ j \end{pmatrix}$。
- $f_{i,\min(j,k)}=f_{i-1,k} \cdot \begin{pmatrix} c_i \\ j \end{pmatrix}+g_{i-1,k}(j-\max(0,j-k))\begin{pmatrix} c_i \\ j \end{pmatrix}$。
把 $\min$ 拆掉，推下式子发现可以前缀和优化，时间复杂度 $O(n)$。
::::
#### CF1870E Another MEX Problem
::::success[Sol]
考虑可行性 dp，转移的时候对于每一个 $i$，枚举前面的每一个 $j$，由结论 4 可得，有效的转移是 $O(n)$ 次的，于是就做完了。
::::