Mex专题

· · 个人记录

月赛被吊打后的 \color{green}\text{tommy} 觉得 \texttt{mex} 这个运算还挺有意思的，就开了这么一个奇怪的专题啦qwq

### P4137 Rmq Problem / mex 和 $\texttt{mex}$ 其实并没有什么关系，就是借助了 $\text{mex}$ 的定义而已。 题目要求对指定区间 $[L,R]$ 求 $\text{mex}$，根据 $\text{mex}$ 定义，我们只需要记录每种数最后一次出现的位置，寻找最小的数 $x$，其最后一次出现的位置 $p\in [1,L)$。 那么建 $n$ 棵线段树，第 $i$ 棵线段树记录 $1\sim i$ 范围内每种权值最后一次出现的位置，询问时就在第 $R$ 棵线段树上二分。 空间会爆怎么办？发现是个经典主席树直接套就行。不需要离散化，因为只有 $[0,n-1]$ 范围内的数会对答案造成贡献。 ### CF1375D Replace by MEX 看到这种 - Please remember that it is **not** required to minimize $k$. 显然是构造题。此题利用了任意一个集合 $S$ 的 $\text{mex}$ 不会是集合 $S$ 中的数这一性质，巧妙的保证了操作次数不会超过 $2n$。 我们可以想到，使用 $\text{mex}$ 构造数列，我们希望通过 $\text{mex}$ 得到一些连续的数的次数尽可能多。那么自然最终得到的序列是 $0,1,2,3,4,..,n-1$，能够满足我们的目的。 接下来用以下的步骤构造这个序列： - 若 $a_i=i-1$，$a_i$ 在最终的位置上，不需要改变 $a_i$ 的值。 - 若当前序列的 $\text{mex}$ 不为 $n$，令 $a_{\text{mex}+1}=\text{mex}$。 - 若当前序列的 $\text{mex}$ 为 $n$，令任意一个 $a_i\neq i-1$ 的 $a_i=\text{mex}$。 下面来证明这样构造的步数一定不会超过 $2n$。 假设所有数都不在自己的位置上，那么最坏情况下我们对于每个数先进行第 $3$ 个操作，再进行第 $2$ 个操作，这种情况下需要 $2n$ 步。 为什么不是先进行第 $2$ 个操作再进行第 $3$ 个操作呢？因为一个数一旦在最终的位置上，就不会再变动了。并且对 $a_i$ 进行一次第 $3$ 个操作后，直到 $a_i$ 的值被赋为 $i-1$ 之前，序列的 $\text{mex}$ 都不可能为 $n$（想一想，根据 $\texttt{mex}$ 的性质）。也就是说，对于序列中任意的 $a_i$，最劣情况下只会被操作两次，先被第 $3$ 个操作赋为 $n$，再被第 $2$ 个操作赋为 $i-1$。 由于 $n\leq 1000$，暴力找 $\text{mex}$ 就可以了。