关于 mex

关于 mex

1.在位置 \(pos\) 插入一个数 \(v\)。

2.询问 \([l,r]\) 的 mex。

可以考虑进行一个二分。二分区间 \([l,mid]\) 内的数是否都出现过。这个可以把 \([l,mid]\) 的数拎出来，考虑算出它们的前驱，维护区间 min，对于询问区间 \([ql,qr]\) ，倘若 \((qr,INF)\) 有一个位置的前驱在 \(ql\) 左侧，就说明这个数没有在 \([ql,qr]\) 中出现过，否则就可以。整体二分可以做到两只 log。

这是对于 mex 问题我们的第一种思路，就是二分。

另一种思路是逆向思考。我们发现 mex 的插入每次复杂度是均摊的，这不够好，但是倘若我们删除呢？每次操作就是把答案跟删为 \(0\) 的数取个 min，是 \(O(1)\) 的，这很好。

上面那道题就有另一种做法了，我们考虑对操作分块，每一块内先假装是这一块的结尾的状态，然后把不在这个区间内的数删掉。配合根号平衡可以做到单根号。

mex 问题还有另一个入手点，就是刚刚说的均摊。例如 Ynoi2015 我回来了。

当然，倘若给你一个集合让你支持动态插入删除，然后查 mex，这个可以做单次 \(O(\log n)\)，考虑用 set 维护不存在的值即可。