区间带异或mex

Keaven · 2023-10-14 12:03:35 · 个人记录

在线解决静态 {\rm mex}_{i=l}^{r}{v_i \oplus x} 问题，O(n log n) 。

1.朴素求mex：

计数排序后扫从 0 开始扫一遍。

2.带插入求全局mex：

需维护 \le v 的数的种数 c_v，询问找最小的 v 使 c_v<v 。

权值线段树可实现：

节点维护对应的值域区间中有多少个出现过，因为只有单点插入，可以去重。

询问时看左区间满没满，满指出现个数等于区间长度。左区间没满则递归左区间，否则递归右区间。递归到的叶子就是 {\rm mex} 。

具体实现可只上传满没满的状态。

3.前缀mex：

对权值线段树可持久化一下。

4.区间mex：

每个数（对应权值线段树的一个叶子节点）记录它出现的最大位置（最右出现的位置），上传时取 \min 记 mn 。

如果一个节点 mn< l ，说明该节点对应的数的区间，存在至少一个数不在序列区间 [l,n] 中，即上文的“没满”状态。

配合上可持久化就实现了区间询问。

5.带异或：

要在权值线段树上实现全局异或修改，那我们想到 01trie ！（01trie 是不是就是满二叉权值线段树呢？）

如果异或修改 x 的第 i 位为 1 ，意味着trie上这一层所有节点左右儿子互换。我们不需要实际的互换，询问的时候把左儿子当作右儿子，把右儿子当作左儿子即可。

6.其他博弈问题：

假设集合的一个元素的 SG 值为它补集的异或和，集合的 SG 值为所有元素 SG 的 {\rm mex}。

需要实现合并两个集合，并维护集合的 SG 值。

我们可以融合前文 2,5 的做法，每个集合对应一颗 01trie 和一个全局异或标记 tag，配合启发式合并解决。

详见这里