fuck

duyi · 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)。

参考代码

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