自动搬运

查看原文

来自洛谷，原作者为

	DreamWasTaken **

搬运于2025-08-24 22:34:08，当前版本为作者最后更新于2021-10-17 16:17:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

莫队二次离线模板题。

直接套 P4887 代码，只需要改变结构和询问：

P4887 中，我们希望 $a_i\oplus a_j$ 属于目标集合 $t$。这里 $a_i\in p$ 其中 $p$ 需要支持添加元素，并且 $a_j$ 随时询问。

于是我们维护了数组 $S$，其中 $S_i$ 为 $p\otimes t$ 中异或为 $i$ 的对数个数。这样询问可以直接访问 $S$ 而修改可以 $O(|t|)$ 修改 $S$ 的 $|t|$ 个位置。

而这道题中 $t$ 为一个前缀 $[0,x]$ 的形式，我们仍然可以维护同样的数组 $S$。将 $a_i$ 添加到集合 $p$ 的时候 $S$ 需要对所有 $S_{a_i\oplus c}:0\le c\le x$ 位置加 1。考虑 $x+1$ 的二进制最大位 $y$，则 $2^y<x$，$c$ 可以分成两类：$0\le c<2^y$ 以及 $2^y\le c<(x+1)\iff 0\le c\oplus2^y<(x+1)\oplus2^y$。

继续拆最大位就可以把 $\{a_o\oplus c\}$ 集合拆为若干 $[l\times 2^k,(l+1)\times 2^k)$ 之并，其中每一个 $k$ 互不相同。对 $S$ 分大小为 $2^9$ 的块，当 $k\ge 9$ 整块暴力打标记，当 $k<9$ 直接暴力修改，询问仍然是 $O(1)$。

这样的时间复杂度为 $O(n\sqrt n+n\sqrt q)$。

代码：

void add(int val) {
  for (int i = 17; i >= 9; i--)
    if (x & (1 << i)) {
      int l = (val >> i) << i;
      int r = l + (1 << i);
      l >>= 9, r >>= 9;
      for (int j = l; j < r; j++)
        layer2[j]++;
      val ^= (1 << i);
    }
  for (int i = 8; i >= 0; i--)
    if (x & (1 << i)) {
      int l = (val >> i) << i;
      int r = l + (1 << i);
      for (int j = l; j < r; j++)
        layer1[j]++;
      val ^= (1 << i);
    }
}