题解：P11160 機械生命体

clx201022 · 2026-08-14 08:50:20 · 题解

博客园版本

题面传送门

操作一和操作二是平凡的，大多数数据结构都支持插入和删除。

题目中的 \operatorname{lowbit} 即为二进制最低位 1 所在的位置，而 0 因为没有 1 所以可以理解为 \operatorname{lowbit} 在无穷远处。

操作四中要想让 \operatorname{lowbit}(x\oplus y) 尽可能大，即 y 的从低位到高位与 x 尽可能相同。由此不难想到用 Trie 从低位到高位维护每个集合中每个数的数量。查询时尽可能寻找低位与 x 相等的 y，未找到时当前位即为 \max_{y\in S}\operatorname{lowbit}(x\oplus y)。

插入和删除可以类比权值线段树，动态开点并在对应位置加一或减一。以上三种操作时间复杂度单次 \mathcal{O}(\log x)。

接下来只剩操作三还没有考虑到。

先考虑 k=1,v=1 的特殊情况。

因为对于任意的 x,y 都有 \operatorname{lowbit}(x\oplus y)\ge 1，所以此操作相当于全局 +1。

如何全局 +1？交换左右子树然后对左子树（即此前的右子树）重复此操作直到到达叶子节点。

为什么？对于每个二进制数，+1 相当于将从低位到高位第一个 0 置 1 并将此前所有 1 置 0。左子树（最低位为 0）+1 后最低位为 1，挪到右子树；右子树（最低位为 1）+1 后最低位置 0 并进位（即递归重复操作）。

设根节点子树中点的集合为 Y，则其儿子子树中的点的集合为 \{y\in Y\mid \lfloor\frac{y}{2}\rfloor\}，左右儿子的区别在于最低位是 0 或 1。

推广到 v\ne 1 的情况。

运用我们惊人的注意力可以注意到 y+v 等价于 2(\lfloor\frac{y}{2}\rfloor+\lfloor\frac{v}{2}\rfloor)+(y\bmod 2)+(v\bmod 2)，因此 +v 可以转化为在根节点执行全局 +(v\bmod 2)（+0 等于没加）后对左右子树执行全局 +\lfloor\frac{v}{2}\rfloor。每次完整执行是 \mathcal{O}(\log^2 x) 的。能否优化？

Trie 的本质就是不带左右端点的权值线段树。因此对于修改我们可以打上标记 lazyTag 代表修改，访问子节点时同步下放即可。优化后时间复杂度均摊 \mathcal{O}(\log x)。