但是我莫队都不是很会欸~

二次离线莫队

顾名思义，就是在原来就离线的莫队上再套一个离线

由 lxl 大佬发明（ lxl 是多爱根号算法啊）

引入

莫队都知道吧？众所周知，莫队的时间是 $O(n \sqrt{n})$ 对吧？

不对！ $O(n \sqrt{n})$ 是在双指针移动跟新答案为 $O(1)$ 的情况下，实际是 $O(n \sqrt{n} \times O(双指针移动跟新答案))$ ，典型的情况是，一个数的贡献为区间内小于它的数的个数（也就是说，一次跟新涉及到一个区间/很多个数），此时每添加/删除一个数的时间就……

那怎么办呢？我们把莫队指针每次移动当成询问，既然在线（即每次移动立刻跟新）是难以保证时间的，那我们就离线解决（这就是第二次离线），一般用扫描线处理，假设 $O(双指针移动跟新答案) = O(k)$ 那么普通莫队的时间为 $O(n k \sqrt{n})$ ，而二次离线的时间复杂度为 $O(nk + n \sqrt{n})$ （其实时间和二次离线后选择的数据结构有关，但一般这都不是瓶颈）

但有前提：移动指针对答案的影响可用前缀写成差分的形式

思想

设函数 $f(x, [l, r])$ 表示“ $x$ 对区间 $[l, r]$ ”的贡献，这个东西不好搞，我们考虑到 $f(x, [l, r]) = f(x, [1, r]) - f(x, [1, l - 1])$ （这里假设了 $f$ 可以差分，一般题目应该都可以，不行的话……那反正蒟蒻我就不会了），那么我们可以把每次移动指针转化为一个数对一个前缀的贡献

设当前状态为 $[l, r]$ ，我们分类讨论：

1. 右端右移，即 $[l, r] \to [l, r + k]$ ，答案改变量为 $\sum _{i = r + 1}^{r + k} f(i, [1, i - 1]) - f(i, [1, l - 1])$
2. 右端左移，即 $[l, r] \to [l, r - k]$ ，答案改变量为 $\sum _{i = r - k + 1}^{r} -(f(i, [1, i - 1]) - f(i, [1, l - 1]))$
3. 左端左移， 即 $[l, r] \to [l - k, r]$ ，答案改变量为 $\sum _{i = l - k}^{l - 1} f(i, [1, r]) - f(i, [1, i])$
4. 左端右移， 即 $[l, r] \to [l + k, r]$ ，答案改变量为 $\sum _{i = l}^{l + k - 1} -(f(i, [1, r]) - f(i, [1, i]))$

看起来感觉还是不能直接算（时间复杂度过高）

我们分开看，第一类， $f(i, [1, i])$ 和 $f(i, [1, i - 1])$ 都是只关于 $i$ 的式子，可以直接预处理

第二类 $f(i, [1, r])$ 和 $f(i, [1, l - 1])$ 不太好搞，考虑打懒标记，给每个数开一个 vector ，若 $x$ 在数 $k$ 的 vector 里，就代表我们要求 $f(x, [1, k])$

由于莫队修改都是连续的，不必真的存一个个的数，而可以存三元组 $(l, r, id)$ 表示“ $\forall x \in [l, r]$ 都要求 $f(x, [1, k])$ 而 $id$ 同时记录符号”

现在来分析时间复杂度，预处理 $f(i, [1, i])$ 和 $f(i, [1, i - 1])$ 是 $O(nk)$ 的，另外可以把它们做一个前缀和，这样询问这一部分总贡献就可以 $O(1)$ 了（卡常技巧一定要记！）

另一部分我们先扫一般每个数，用时 $O(n)$ ，当扫到 $[1, i]$ 时，就去把点 $i$ 里面记录的询问全部计算了，由于莫队指针移动次数是 $O(n \sqrt{n})$ 的，所以查询次数是 $O(n \sqrt{n})$ ，我们用某种数据结构维护它，这个数据结构要修改 $O(n)$ 次，询问 $O(n \sqrt{n})$ 次，我们使用一种修改较慢但查询较快的数据结构，可以做到 $O(np + nq\sqrt{n})$ ，其中 $p, q$ 是修改和查询的时间，在大部分题中 $p \le \sqrt{n}$ ， $q$ 约为 $1$

综上，二次离线部分时间复杂度为 $O(nk + n\sqrt{n})$ ，加上前面莫队的 $O(n \sqrt{n})$ ，时间复杂度为 $O(nk + n\sqrt{n})$

最后注意 $f(x, [l, r])$ 不是答案！是变化量！所以最后要前缀和一下

例题

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

题意

给定长度为 $n \le 10^5$ 的序列 $a_i < 16384(2^{14})$ ， $m \le 10^5$ 次寻问区间 $[l, r]$ ，查询 $l \le i < j \le r$ 且满足 $a_i \oplus a_j$ 在二进制下恰有 $k < 16384$ 个 $1$ 的二元组 $(i, j)$ 有多少对（这里 $k$ 是一开始就固定的，每次询问都一样）

思路

二次离线的板子（从题目就看出来了），考虑二次离线部分：

考虑预处理 $f(i, [1, i - 1])$ ，另外一个同理，具体地，扫描一遍数列，枚举二进制下有 $k$ 个 $1$ 的数（卡常可以预处理），对于每个 $i$ ，查一下 $cnt[i \oplus x]$ （ $x$ 二进制下有 $k$ 个 $1$ ）即可

对于第二类，我们就用一个数组 $t[z]$ 表示当前前缀中的数异或 $z$ 后得到的数恰好有 $k$ 个 $1$ 的数的个数，同样直接查，修改和查询都是 $O(1)$ 的

然后……就结束了！ lxl 这题不卡常，我爱 lxl ！

代码

#include <bits/stdc++.h>
#define STC static
using LL = long long;
const int N = 1e5 + 5, V = (1 << 14), B = 320;
struct Ques
{
    int l, r, id;
    LL ans;
} q[N];
struct Tuple{ int l, r, id; };
std::vector<Tuple> tag[N];
std::vector<int> xk; //有k个1的数
int n, m, k, bid[N], a[N]; //bid:块号加
LL ans[N], f[2][N]; //f:存第1类,第二类不存,直接
void prev()
{
    for (int i = 0; i < V; ++i) if (__builtin_popcount(i) == k) xk.push_back(i);
    for (int i = 1; i <= n; ++i) bid[i] = (i - 1) / B + 1;
    std::sort(q + 1, q + m + 1, [&](Ques a, Ques b){ return bid[a.l] == bid[b.l] ? a.r < b.r : a.l < b.l; });
}
void add_tag() //模拟莫队,给第2类打标记
{
    for (int i = 1, il = q[1].r + 1, ir = q[1].r, l, r; i <= m; ++i)
    {
        l = q[i].l, r = q[i].r;
        if (il > l) tag[ir].push_back({l, il - 1, i});
		else if (il < l) tag[ir].push_back({il, l - 1, -i});
		il = l; //这里注意il变了
        if (ir < r) tag[il - 1].push_back({ir + 1, r, -i});
        else if (ir > r) tag[il - 1].push_back({r + 1, ir, i});
		ir = r;
	}
}
void offline() //二次离线求第1、2类
{
    STC int t[V];
    for (int i = 1; i <= n; ++i)
    {
        f[0][i] = f[0][i - 1] + t[a[i]]; //这里顺便就前缀和了
        for (int x : xk) ++t[x ^ a[i]];
        f[1][i] = f[1][i - 1] + t[a[i]];
        for (auto tg : tag[i]) //求第二类
            for (int j = tg.l, k = tg.id < 0 ? -1 : 1; j <= tg.r; ++j) q[tg.id * k].ans += t[a[j]] * k;
    }
}
void modui() //真的莫队
{
    for (int i = 1, il = q[1].r + 1, ir = q[1].r, l, r; i <= m; ++i)
    {
        l = q[i].l, r = q[i].r;
        if (il != l) q[i].ans += f[1][l - 1] - f[1][il - 1];
		il = l;
        if (ir != r) q[i].ans += f[0][r] - f[0][ir];
		ir = r;
	}
    for (int i = 2; i <= m; ++i) q[i].ans += q[i - 1].ans;
    for (int i = 1; i <= m; ++i) ans[q[i].id] = q[i].ans;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) scanf("%d %d", &q[i].l, &q[i].r), q[i].id = i;
    prev(), add_tag(), offline(), modui();
    for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
    return 0;
}

废话

luogu AC $400$ 祭（然鹅只有 rusun 巨佬 AC 数的一半）