CF1515H Phoenix and Bits 分析

__ryp__ · 2024-08-11 20:34:46 · 个人记录

我们考虑异或操作怎么做。

显然的，放到 Trie 上头按位考虑，那么实际上就是交换了每一个 x 为一的位对应的子树，打标记就可以了。

这个标记需要存储的是所异或的 x，并且在每次 push_down 时，要一直下放整条链。

注意到 A 与 B，等于 \overline A 或上 \overline B 的补，也就是只要有一个位置为零，这一位就是零。所以我们就解决或操作就好了。

或上 x，就是说如果某一位 x 为一，这一位对应的 0 子树就要合并到 1 子树上头。如果这个子树是满的，我们就暴力合并；否则，就要打标记。

留着之后写吧。