P7470 [NOI Online 2021 提高组] 岛屿探险

PPL_ · 2021-03-27 16:05:50 · 题解

前言

说实话，我并不知道我用的这个做法叫什么，我开始以为他是整体二分，然后发现我写出来的东西可能是线段树分治(然而我根本就不知道线段树分治是个啥)。

而且这个做法可能被卡，因为我本题测出来极限数据为2.9s，卡常后为2.4s。不过这份代码暂时可以在洛谷上过民间数据。

题目

洛谷

讲解

本来这道题我是一点都不会的，但是我们完全可以根据套路把这道题做出来，我直接把草稿搬上来(部分删改)：

显然这道题要离线。

由于这个 \tt min 很不好搞，猜测是对 d 进行排序，然后用数据结构维护 a\oplus c ，最后分别算最小值是 b 或者 d 的两个部分的贡献。

考虑把询问丢到线段树上面，也就是把每个询问分成约 log_2n 个，放到线段树上，这样我们如果可以处理出每个区间对应的询问，那么我们就可以做到 O(nlog_2nlog_2w) 了。

之后的讲解如果提到全部询问等字眼，指的是线段树中某个区间的全部询问。

这里我把取等条件是算在 d 里面的。

把式子写在这里：a_i\oplus c \le min(b_i,d) (c,d没有下标相当于我们考虑信息多组，询问为一组)。

part1 d \le b_i

这个部分要简单一些，我们只需要把所有的 (a_i,b_i) 按 b_i 排序，然后把满足 d\le b_i 的 a_i 扔到字典树里面去。

显然所有询问 (c,d) 也需要排序，用 two-pointer 维护插入的信息。

对于每个询问我们把一组 (c,d) 扔进去跑即可。

part2 b_i < d

在上一个部分我们根据 a_i,c,d 可以算出有多少个位置满足条件，但是现在我们的信息是 a_i,b_i,c，存在两个变元，这个又怎么做呢？

emmm，知3求2，我们可以把 a_i,b_i 扔到字典树里面去，显然我们可以推出 c 在某个范围是可以得到贡献的，最后把 c 放进去跑，累加答案即可。

当然这里我们依然要对 (a_i,b_i) 排序，只是这个时候要扔到字典树里面的是 b_i < d 的 (a_i,b_i)。

排序之后依然可以用 \tt two-pointer 维护插入的信息，但是这里我们发现上面插入的和这里插入的信息互为补集，所以我们需要先把part1的信息全部插入，然后按顺序插入part2的信息，删除part1的信息。

具体的，对于这棵字典树，我们这样操作(a 是 a_i 二进制下当前位置的数字,b,c 同理)：

更新字典树的过程是抵着上限的(仔细揣摩这句话)，也就是说在之前 a_i 和 b_i 是相等的。