P7906 [Ynoi2005] rpxleqxq

· · 题解

莫队二次离线模板题。

直接套 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);
    }
}