二次离线莫涛

__biu_biu_biu__ · 2026-05-06 16:50:15 · 算法·理论

前情提要，前置知识：扫描线，莫队。

二次离线莫队

为了方便，我们将 f(l,r,x) 表示点 x 对区间 [l,r] 的贡献。

对于普通二维莫队，时间复杂度是 O(n\sqrt{m}f) 的，其中 O(f) 是单次操作修改复杂度。而二次离线莫队可以将一些满足特定条件的问题的复杂度降低至 O(nf+n\sqrt{m})。

所谓的“特定条件”其实就是满足单次修改可以进行拆分，即 f(l,r,x)=f(1,r,x)-f(1,l-1,x)，例如：

• 逆序对。显然点 x 对区间 [l,r] 的逆序对贡献为 x 对区间 [1,r] 的贡献减去区间 [1,l-1] 的贡献。
• 求 a_i | a_j 的 (i,j) 的个数。这个也是显然的。
• 求 a_i \oplus a_j\le k 的个数。这个也很显然。

对于莫队中的区间推移，假设此时的区间为 [l,r]，则对于区间更新：

• 要更新区间 [l,r+k]，则答案更新了 \sum\limits_{i=r+1}^{r+k}f(1,i-1,i)-f(1,l-1,i)。
• 要更新区间 [l,r-k]，则答案更新了 -\sum\limits_{i=r-k+1}^{r}f(1,i-1,i)-f(1,l-1,i)。
• 要更新区间 [l+k,r]，则答案更新了 -\sum\limits_{i=l}^{l+k-1}f(1,r,i)-f(1,i-1,i)。
• 要更新区间 [l-k,r]，则答案更新了 \sum\limits_{i=l-k}^{l-1}f(1,r,i)-f(1,i-1,i)。

这就是对于一个询问中莫队要做的事：将 f 提取出来，交给扫描线处理。

接下来是扫描线部分。

对于每一个点 i，需要存储所有的 [l,r] 表示在莫队中更新的 f(l,r,i)，一共需要存储 4 个信息，分别是所对的查询 id，对于答案的贡献是增加还是减少 k\in\{-1,1\}，以及 l,r 表示更新的范围。

然后剩下的部分常规扫描线加上一个处理问题的数据结构即可。

但是此时还有一个问题，我们的修改总数量是 O(n)，但是查询数量是 O(n\sqrt{q}) 的，此时的时间复杂度仍是 O(n\sqrt{q}f) 的，所以此时我们可以利用分块等数据结构，将修改的复杂度从 O(f) 提升至 O(\sqrt{n})，然后将查询的复杂度降低至 O(1)，实现了根号平衡。

总结：莫队二次离线将处理过程中的更改区间通过扫描线变为两部分：修改和查询；然后使用根号平衡等算法将多次查询的复杂度降低，少量修改的复杂度提升，以平衡时间复杂度。

莫队二次离线例题

P4887 【模板】莫队二次离线 / 第十四分块(前体)

考虑莫队。

我们要求 a_i\oplus a_j 恰好有 k 个 1 的 (i,j)，由于实际上有用的 k 很少，所以可以暴力跑出二进制下有 k 个 1 的个数的数，一共是 (^{14}_{\log n}) 个，直接莫队的话是 O(n\sqrt{m}(^{14}_{\log n}))，会超时。

显然此时的修改是可以支持拆分的。我们将所有询问存储下来，一共只有 n 种不同的修改，再暴力跑修改即可，时间复杂度 O(n(^{14}_{\log n})+n\sqrt m) 的。

P5047

使用朴素莫队套树状数组显然超时。考虑优化。

修改可以拆分，考虑二次离线。

在拆分完毕以后，我们现在有 O(n) 个修改，O(n\sqrt{m}) 个查询。无疑问的，我们需要支持修改复杂度 <O(\sqrt{n})，查询复杂度 O(1) 的算法。

可以使用值域分块代替值域树状数组。

我们记录前 k 个块的和，那么查询显然可以 O(1) 做到。设查询的数为 x，位于第 k 个块，那么答案为 sum_{k-1}+sub_x。

对于修改，可以直接暴力修改块的前缀和，复杂度 O(\sqrt n)，对于块内的仍然暴力修改，复杂度 O(\sqrt n)。

总复杂度 O(n\sqrt n+n\sqrt m)。