自动搬运

查看原文

来自洛谷，原作者为

	duyi 大家好我是于之航爸爸

搬运于2025-08-24 22:30:10，当前版本为作者最后更新于2021-03-27 14:49:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

噜啦噜啦咧，噜啦噜啦咧的阅读体验

「NOI Online 2021 #1」岛屿探险

题目大意

给定一排 $n$ 个元素，每个元素有两个属性：$a_i, b_i$。

有 $q$ 次询问，每次询问给出四个参数 $l_j, r_j, c_j, d_j$。问区间 $[l, r]$ 里满足 $a_i\operatorname{xor} c_j \leq \min\{b_i, d_j\}$ 的 $i$ 有多少个。

数据范围：$1\leq n,q\leq 10^5$，$1\leq l_j\leq r_j\leq n$，$0\leq a_i, b_i, c_j, d_j\leq 2^{24} - 1$。

本题题解

0. 约定

设 $m = \max\{a_i, b_i, c_j, d_j\}$，这是分析复杂度用的。

1. 分析一次询问

对于一次询问 $l_j, r_j, c_j, d_j$，考虑把 $i$ 分为 $b_i > d_j$ 和 $b_i\leq d_j$ 两类，分别统计答案。

1.1. b[i] > d[j] 的 i

对于 $b_i > d_j$ 的 $i$，答案是 $\sum_{i} [a_i \operatorname{xor} c_j\leq d_j]$。此时的特点是：答案与 $b_i$ 无关。考虑把这些 $a_i$ 插入到一个 $\text{01 trie}$ 中：也就是按二进制从高位到低位的顺序，把 $a_i$ 当成一个 $01$ 串。我们在 $\text{01 trie}$ 上从根往下走（也就是按二进制从高位向低位走），对于当前节点，假设它深度为 $h$，那么它代表的值等于 $c_j\operatorname{xor}d_j$ 的前 $h$ 高位。考虑下一位：

• 如果 $d_j$ 的下一位为 $0$，那么说明 $a_i$ 的下一位必须和 $c_j$ 的下一位相等（否则 $a_i \operatorname{xor} c_j > d_j$，不满足要求），我们直接向这个方向走即可。
• 如果 $d_j$ 的下一位为 $1$，那么有两种可能：
  • 如果 $a_i$ 的下一位和 $c_j$ 的下一位相等，那么无论 $a_i$ 后面更低的位上填什么，都一定满足：$a_i\operatorname{xor} c_j < d_j$。所以 $a_i$ 后面的位可以任意填，方案数就是这一整棵子树里 $a_i$ 的个数之和。
  • 如果 $a_i$ 的下一位和 $c_j$ 的下一位不相等，那么此时 $a_i$ 仍然是等于 $c_j \operatorname{xor} d_j$ 的。我们向这个方向走过去，然后考虑更低的位即可。

1.2. b[i] <= d[j] 的 i

对于 $b_i \leq d_j$ 的 $i$，答案是 $\sum_{i} [a_i \operatorname{xor} c_j\leq b_i]$。看到限制里既有 $a_i$，又有 $b_i$，我们难以把它们放到同一个数据结构里去，所以很难实现查询。换个角度考虑：观察 $a_i\operatorname{xor} c_j \leq \min\{b_i, d_j\}$ 这个式子，你会发现 $(a, b)$ 和 $(c, d)$ 是对称的。那么，把修改当成询问做，询问当成修改做，是不是就和 1.1. 的情况一样了呢？

具体来说，我们将询问离线，把所有 $c_j$，按上述方法（和上面的 $a_i$ 一样）插入一个 $\text{01 trie}$ 中。然后对每组 $(a_i, b_i)$，把它当成上面的 $(c_j, d_j)$，在 $\text{01 trie}$ 上“查询”。当然，我们其实不是要查询一个结果，而是要把它“贡献”到符合条件的 $c_j$ 里。在 1.1, 里，我们遇到一整棵符合条件的子树，就把这个子树里 $a_i$ 的数量加入答案中；而现在，我们遇到一整棵符合条件的子树，就在该节点处打一个标记，表示令子树里所有 $c_j$ 的答案加上 $1$。最后，每个 $j$ 的答案，就是 $c_j$ 到根路径上的标记之和。

2. 多次询问时

当然我们不可能每次询问都重新建两个 $\text{trie}$，那样时间复杂度是 $\mathcal{O}(qn\log m)$，还不如暴力。

考虑一个简化的问题：如果只有 $b_i > d_j$ 的 $i$（也就是测试点 $5\sim 7$），那么可以在所有询问开始前，先建好一个可持久化 $\text{trie}$。则查询时，将 $r_j$ 和 $l_j - 1$ 两个时刻的 $\text{trie}$ 上查询的结果相减即可。时间复杂度 $\mathcal{O}(q\log m)$。

考虑另一个简化的问题：如果只有 $b_i \leq d_j$ 的 $i$（也就是测试点 $8\sim 11$），那么可以先将询问离线，建出所有 $c_j$ 的 $\text{trie}$。然后将询问拆成两个：$[1, r_j]$ 和 $[1, l_j - 1]$（相减得到答案）。现在所有询问的左端点都是 $1$。将询问按右端点排序，从小到大扫描。每次加入当前的 $i$（如前文所述，这个加入操作有点像 1.1. 里的查询操作，只不过把查询变成了打标记），然后对右端点为 $i$ 的询问统计答案。时间复杂度 $\mathcal{O}(q\log m)$。

上述两种情况我们都会做了，那么现在唯一的问题是，怎么把 $b_i > d_j$ 的 $i$ 和 $b_i\leq d_j$ 的 $i$ 分离出来。考虑把所有 $b_i, d_j$ 放在一起排序（特别地，$b_i, d_j$ 想到时，$b_i$ 放在前）。然后做 $\text{cdq}$ 分治。那么每次只需要考虑右半边对左半边的贡献。具体来说，取出右半边的所有 $a_i$，左半边的所有 $(c_j,d_j)$，按情况 1.1. 的方法做一次；再取出右半边的所有 $c_j$，左半边的所有 $(a_i,b_i)$，按情况 1.2. 的方法做一次。就求出所有答案了。

每层分治时，做问题 1.1. 和 1.2.，时间复杂度是 $\mathcal{O}(\mathrm{len}\log m)$（$\mathrm{len}$ 是当前分治区间的长度），所以总时间复杂度 $\mathcal{O}((n + q)\cdot \log (n + q)\cdot \log m)$。

参考代码

勇敢向前进，前进有奖品！！！！