莫队二次离线
简介
此处定义更新复杂度为单次移动 $l,r$ 指针所需的时间复杂度，查询复杂度为当莫队左右端点移动到查询位置时获得答案所需的时间复杂度。
当莫队更新时间复杂度较高而查询复杂度较低时，莫队二次离线能平衡时间复杂度。本质上是将普通莫队 $O(n\sqrt n)$ 次更新，$O(n)$ 次查询平衡为 $O(n)$ 次更新，$O(n\sqrt n)$ 次查询。
莫队二次离线要求贡献具有可减性，并且查询复杂度极低，能达到 $O(\log n)\sim O(1)$。一般多用于数对统计问题。
实现
莫队二次离线实现方式很多，此处仅介绍一种空间复杂度 $O(n)$，较为好写的方式。莫队有 $4$ 个转移方向，即 $r$ 右移，$l$ 左移，$r$ 左移，$l$ 右移。此处仅讨论 $r$ 右移，其余三种方向与之类似。
讨论从 $[l,r_1]$ 转移到 $[l,r_2] (r_2>r_1)$。设 $f(x,l,r)$ 表示 $a_x$ 对 $a_l,a_{l+1},\cdots a_r$ 的贡献。相对于原区间，则增量为 $\sum_{i=r_1+1}^{r_2}f(i,l,i-1)$。因为贡献具有可减性，则可表示为 $\sum_{i=r_1+1}^{r_2}f(i,1,i-1)-\sum_{i=r_1+1}^{r_2}f(i,1,l-1)$。即橙色区间中每个数对它的前缀的贡献减去其对蓝色区间的贡献。
假设更新时间复杂度为 $O(k)$，查询时间复杂度 $O(1)$。首先 $i$ 从 $1$ 到 $n$ 枚举每个 $a_i$，计算出其对其前缀的贡献 $f_i$，然后用 $a_i$ 更新答案。时间复杂度 $O(kn)$。
像普通莫队一样排序，遍历每个询问。在计算两个询问之间的增量时，第一部分即为一段 $f$ 的和，在之前已经预处理，直接求和。而另一部分则为橙色区间对蓝色区间（一段前缀）的贡献。我们可以将橙色区间的左右端点挂到蓝色区间的右端点处，稍后处理。时间复杂度 $O(n\sqrt n)\sim O(n)$。（取决于 $f$ 是否计算了前缀和。）
再次 $i$ 从 $1$ 到 $n$，枚举每个 $a_i$，用其更新答案，在遍历挂到该位置上所有区间中的每个位置，计算贡献。时间复杂度 $O(n\sqrt n+kn)$。
由于此时计算的是每个询问与上个询问的增量，所以要对所有增量做前缀和才能得到询问的答案。总时间复杂度 $O(n\sqrt n+kn)$。
例题
P4887【模板】莫队二次离线（第十四分块（前体））
题目描述
序列 $a$，每次查询给一个区间 $[l,r]$，查询 $l\leq i<j\leq r$，且 $a_i\oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。$\oplus$ 是指按位异或。$1\leq n,m\leq100000$，$0\leq a_i,k<16384$。时间限制 $\rm{1s}$，内存限制 $40\rm{MB}$。
解法
$16384=2^{14}$，所以 $k>14$ 时答案是 $0$，需要特判。当 $k\le14$ 时有 $\binom{14}{k}$ 种合法的异或结果。在加入一个数时，枚举可能的 $\binom{14}{k}$ 种结果 $x$，则 $a_i$ 对所有的 $a_i\oplus x$ 均可产生贡献。维护一个桶 $t$，$t_i$ 表示能对 $i$ 产生贡献的数字个数。查询 $O(1)$，更新时枚举 $x$，$t_{a_i\oplus x}$ 增加 $1$。时间复杂度 $O(\binom{14}{k})$。使用莫队二次离线即可，时间复杂度 $O(n\sqrt n+\binom{14}{k}n)$。
Code
1 | |
[LnOI2019]来者不拒，去者不追
题目描述
序列 $a$，$m$ 个询问，每次给定区间 $[l,r]$，定义 $f(x)=\sum_{i=l}^r[a_i< x]+1$，求 $\sum_{i=l}^rf(a_i)\times a_i$。$1\le a_i\le10^5,1\le n,m\le5\times10^5$，时间限制 $\rm{5s}$，空间限制 $\rm{250MB}$。
解法
考虑在已有区间中加入一个数 $a_i$，则对当前答案的影响为当前区间内比 $a_i$ 大的数之和以及小于 $a_i$ 的数字个数之和 $+1$。维护两个值域分块，可做到 $O(\sqrt v)$ 单点加，$O(1)$ 求区间和。由于该权值满足可减性，故可以用莫队二次离线优化，时间复杂度 $O(n\sqrt n+n\sqrt v)$。
Code
1 | |