二次离线莫队学习笔记

orz_z · 2022-02-04 23:19:49 · 题解

二次离线莫队

算法提出

二次离线莫队是一个由 lxl 大佬提出的新科技，其基于莫队 + 扫描线的思想，通过扫描线，再次将更新答案的过程离线处理，降低时间复杂度。

具体地，设更新答案的复杂度为 \mathcal O(k)，那么它可以将莫队的复杂度从 \mathcal O(nk\sqrt n) 降到了 \mathcal O(nk+n\sqrt n)， 大大简化了计算。

再补充一点，二次离线莫队通常适用于满足以下条件的题目：

• 可用莫队做。
• 莫队扩展或者删除一个点对答案的影响取决于当前区间的长度。
• 扩展或者删除一个点对答案的影响可用前缀写成差分的形式。

算法解决

以 模板题 为例。

给了你一个序列 a，每次查询给一个区间 [l,r]，查询 l \leq i< j \leq r，且 a_i \oplus a_j 的二进制表示下有 k 个 1 的二元组 (i,j) 的个数。

首先明确，这题如果用普通莫队的话，每一次移动指针的时候需要用 \mathcal O(C_{14}^k) 的复杂度来转移，显然过不去，于是考虑二次离线莫队。

设 a_x 对区间 [l,r] 的贡献为 f(x,[l,r])。

我们考虑区间端点变化对答案的影响，以 [l,r] 变成 [l,r+k] 为例，答案增加了 \sum\limits_{i=r+1}^{r+k}f(i,[l,i-1])。

我们发现，f(i,[l,i-1]) 可以差分成 f(i,[1,i-1])-f(i,[1,l-1])。

这样转移区间的贡献就分为两类：

1. 一个前缀和它后面一个数的贡献，这可以预处理出来。
2. 区间 [r+1,r+k] 对前缀 [1,l-1] 的贡献，保存下来用扫描线做即可。

对于其他情况，大力讨论即可，下面给出结论：

• 右端点右移，[l,r] 变成 [l,r+k]，答案增加了\sum\limits_{i=r+1}^{r+k}f(i,[1,i-1])-f(i,[1,l-1])。
• 右端点左移，[l,r] 变成 [l,r-k]，答案减少了 \sum\limits_{i=r-k+1}^{r}f(i,[1,i-1])-f(i,[1,l-1])。
• 左端点右移，[l,r] 变成 [l+k,r]，答案减少了 \sum\limits_{i=l}^{l+k-1}f(i,[1,r])-f(i,[1,i])。
• 左端点左移，[l,r] 变成 [l-k,r]，答案增加了 \sum\limits_{i=l-k}^{l-1}f(i,[1,r])-f(i,[1,i])。

再看扫描线部分。

我们对于每个前缀 [1,i] 开一个 vector，其中装二元组 (l_0,r_0)（对应上面的 [r+1,r+k]）（另外还要装一个 id，如果 id<0，代表减法，否则代表加法，贡献加到 \mid i \mid 这里去）。

假设当前前缀为 [1,i]，二元组为 (l_0,r_0)，设 t[z] 表示当前前缀中的数异或 z 后得到的数恰好有 k 个 1 的数的个数。

再根据异或的一个性质：若 a\oplus b=c，则有 b \oplus c=a,a \oplus c=b。

所以插入一个 p 值时，就 \mathcal O(C_{14}^{k}) 枚举所有二进制表示下有 k 个 1 的数 val，然后令 t[p \oplus val]++ 即可（第一类贡献的预处理也用这种方法）。

询问时答案即为 \sum\limits_{i=l_0}^{r_o}t[i]。

对于 f(i,[1,i])，由于 i \oplus i=0 且 i=j 这个贡献不算，这可以转为 f(i,[1,i-1])，再加个特判即可。

由于第二类贡献需要先跑一次莫队记录 l_0,r_0（顺便加上第一类贡献），然后再跑一次扫描线计算，相当于再次离线，所以我们通常称以上算法为二次离线莫队。

可以发现，莫队部分时间复杂度为 \mathcal O(n\sqrt n)，当然也可以前缀和优化成 \mathcal O(n)，扫描线部分时间复杂度为 \mathcal O(n\sqrt n+n C_{14}^k)，所以总时间复杂度为 \mathcal O(n\sqrt n+n C_{14}^k)，可过。