Luogu6562 [SBCOI2020] 归家之路

题意：定义一种布尔类型运算 ：如果在 的二进制表示中，满足每一个 是 的位， 的对应位也是 ，那么 为 True , 否则为 False。

维护一个长度为 ，标号为 的序列 ，支持如下操作。

• 给出 ，将所有满足 的 加上 。

• 给出 ，查询 。

，，时限 。

---

有趣的题目。

无修改

称 ，我们要研究这个集合的结构。 询问相当于：指定若干位 （）为 ，若干位（） 为 ，其余位（）随意。

这样，可能的 的个数就是 。当然， 仍然有可能较大。

当 （不确定的位的个数） 较大时，确定的位相应地较少。

设 表示钦定位集合 为 ，位集合 为 的位置的和。

当 时，相当于子集求和，提前 预处理即可。

否则，设 为 中任意一个元素，有：

意思是，用 的方案减去 的方案，即可得到 的方案。

利用这个式子递推，复杂度为 。

和暴力求和结合，复杂度为 。似乎也可以做到 。

---

考虑修改

接下来考虑带修的情况。对时间分块，块大小设为 。

• 零散的 个修改对询问的贡献。

  相当于我们要计算两个形如 的集合的交集。

  假设 中指定位集合 为 ，位集合 为 。 中类似。

  同时属于 相当于指定 为 ， 为 。

每过 个修改就重新计算一次 以及 的子集和。

可以用同样的递推方式将一次加法操作转化为对 个子集的加法，或者是单点加法。

使用高维后缀和即可批量计算子集加法。

这样的复杂度是 取 可得复杂度为 。

常数较小。