Mex 的常见用法和性质。

· · 算法·理论

- 根据定义，$mex = x$ 的集合中一定有 $0$ 到 $x - 1$，且没有 $x$。 - 一个大小为 $n$ 的集合的 $mex$ 最大为 $n$。 - 一个序列的极小的 $mex = x(x \in [0, n])$ 的区间数量不超过 $2n$。 区间 $mex$ 的求法： 1. 离线下来用莫队，里面用值域分块平衡复杂度 $\mathcal O(n \sqrt n)$。 2. 扫描线 $r$ ，用线段树维护 $lst_x$ 表示 $a_l = x$ 的最大的 $l$，可以发现查询直接线段树二分即可。想要在线可以把线段树改成主席树，时间复杂度 $\mathcal O(n \log n)$。 如何找出所有极小的 $mex = x$ 的区间？ 考虑预处理 $mex = 0$ 和 $mex = 1$ 的极小区间。对于 $mex = x$ 的极小区间 $[l, r]$，可以找出左边最近的 $a_i = x$，和右边最近的 $a_i = x$ 的位置，然后把被包含的删掉。由于最后的个数只有 $2n$ 个，而每一次这种区间只会找到两个疑似极小区间，所以一共只找了 $4n$ 个区间，找的过程用数据结构维护。时间复杂度 $\mathcal O(n \log n)$。