CF765F 题解
题目大意
- 维护长度为
n(1 \le n \le 10^5) 的整数序列a(1 \le a_i \le 10^9) ，支持m(1 \le m\le 3 \times 10^5) 个以下查询： - 给出
l,r(1 \le l \le r \le n) ，输出对于i,j \in [l,r] ，且满足i \ne j ，|a_i-a_j| 的最小值。
简要做法
- 看到允许离线，考虑离散化后莫队。
- 现在问题变成了：维护一个集合，支持加数删数，找一个数的前驱后继。
- 很显然，我们可以用树状数组或者
std::set等维护这个集合，但是这样会让时间复杂度变为O(n \sqrt m \log n) ，无法通过此题。 - 我们换一种思路，直接把莫队换成回滚莫队（只加不删），同时值域分块。
- 考虑把查询时的贡献分为两类：来自不同块的和来自相同块的。不同块的可以在每个块内记录最小值和最大值来很方便的维护，问题是如何维护来自相同块的数的贡献。
- 我们可以直接把值域分块换成一个 bitset，然后用 bitset 的
_Find_next来找到一个数的后继。前驱的维护同后继，可以开一个反向的 bitset 来维护。 - 我们设定值域分块的块长为
B ，这样的话移动一次莫队端点的时间复杂度为O(\dfrac B w) ，查询时的时间复杂度为O(\dfrac n B) 。 - 设定莫队块长为
\left \lceil \dfrac n{\sqrt m} \right\rceil ，则时间复杂度为O(\dfrac{n \sqrt mB}w + \dfrac{nm}B) ，当B=256 时速度较快，可以通过此题。
代码参考