P1527 | 你说得对，但是本题为「Forced Online Queries Problem」

Moeebius · 2023-12-20 23:08:45 · 题解

你说得对，但是可以在线的题为什么要离线做呢？

鸣谢 @Querainy

考虑直接将经典的整体二分进行在线化处理：具体地，外层维护一棵权值线段树，结点 [l, r] 内维护所有落在这一区间内的数；询问时直接在上面二分即可。

下面看看内层节点需要支持什么。容易发现只需要二维数点。如果暴力搞一棵主席树，空间复杂度达到 O(n \log^2 n)，无法通过。

权值线段树的一只 \log 已经无法优化了，考虑把主席树的 \log 飞了！

发现我们只要 二维数点。那么我们有一个更加优秀的结构：Wavelet Tree。

Wavelet Tree 是一种非常好写的数据结构，可以理解为 \text{linear space} 的一棵归并树。

考虑归并树状物在做什么。对于每一层，有用的信息其实只有 O(n) 个 bit——每个数是来自于左子树还是右子树。那么我们可以将 w 个 bit 压到一起去，在 WRM（w\ge\log n）下可以认为做到了线性空间。

具体而言，我们从高位往低位扫一遍，每次按当前位 0/1 将序列划分成左右两段进行建树：

（从原论文里截的图，此处 rank 是数出现前缀次数，quantile 是区间求解 kth，与本题无关）

每次询问的时候，相当于数 [l, r] 中 [x, y] 内的数出现次数；考察 Wavelet Tree 在 [l, r] 内数的 值域 范围 [p, q]。

• 如果 [p, q] 被 [x, y] 完全包含，那么返回 r - l + 1。
• 如果 [p, q] 与 [x, y] 无交，返回 0。
• 否则，递归到左右子树。注意到左右子树中 [l, r] 的下标是好维护的：当前层 x 在左子树中对应下标是 \text{count}_0(1, x)，在右子树中则是 \text{count}_1(1, x) + \text{count}_0(1, n)，其中 \text{count}_0(l, r) 表示下标 [l, r] 中数在当前位中 0 出现次数，\text{count}_1 同理。

可以证明上述过程的时间复杂度是 O(\log n) 的，证明与线段树类似。

实现的时候一般不会显式把树建出来；维护当前层的 0-1 串即可。

另外为了处理横坐标重复的问题，可以暴力拆成多个横坐标，复杂度不变。

离散化完直接做就好了，时间 O(q \log^2 n)，空间 O(n \log n)。

然后提交完发现 MTLE 了。原因是：压位数据结构在 n \le w 时表现极差。这部分暴力做就好了。然后外层线段树要写 2 倍空间常数的，否则会差 20 MiB 左右。

如果你愿意的话也可以丢掉外层线段树的高 \log \log n 层。也许可以卡点常（？）

Code，无需刻意卡常即可通过。