[NOI Online 2021 提高组]岛屿探险 题解

· · 个人记录

考虑几个不存在的部分分：

此时要求 (a\oplus c) \le b。

对于每一个 a，它满足要求的 c 一定可以被划分成至多 \log_2 v 个连续区间，且这些区间的长度都是 2 的次幂。

这是为什么呢？你手玩一下 trie 就知道了。

体现在 trie 树上，等于若干个不相交的子树内的点都可以选。

所以对这些点打上标记，查询直接在 trie 树上走到 c 所在的位置，一路经过的标记数量就是答案。

此时要求 (a \oplus c) \le d。

trie 裸题，直接做。

正解？

把前面两个部分合起来。

对于区间询问，我们差分答案就行。

对于动态加 (a,b) 二元组，用 CDQ 就行了。