【学习笔记】二次离线莫队

学习笔记

最近规划的是多做锻炼思维模式的 CF、AT 题，但是这玩意既然 xtr 学长介绍了那为何不学呢？

普通莫队加入/删除一个位置的贡献是 $T(n)$，复杂度 $O(n\sqrt{n}T(n))$，$T(n)$ 很大的时候就 GG 了。。

于是，神说：要有二次离线莫队。

以模板题为例，设 $f(i, [l, r])$ 表示 $i$ 对 $[l, r]$ 所产生的贡献。一次移动只会加入 $l - 1$ 或 $r + 1$，以 $r + 1$ 为例，$f(r + 1, [l, r]) = f(r + 1, [1, r]) - f(r + 1, [1, l - 1])$，前面那项可以预处理（根据 $a xor b = c \Leftrightarrow a xor c = b$，我们可以将有 $K$ 个 $1$ 的 $c$ 的 $a xor c$ 存在桶里，到 $b$ 就直接查），后面这个就要第二次离线下来最后统一做。所以二次离线莫队这玩意实际上减小了「处理答案的变化量」的复杂度。复杂度变为 $O(nT(n) + n\sqrt{n})$。

讲一下第二次离线。你可以把 $f(x, [1, l - 1])$ 放在下标为 $l - 1$ 的 vector 里然后从前往后做，但这样空间是 $O(m\sqrt{n})$ 的。不如维护 $(L, R, q[i].l - 1, i, 1/-1)$ 表示当前统计 $x \in [L, R]$ 对 $[1, q[i].l - 1]$ 产生的贡献、来自第 $i$ 个询问时产生的答案变化量、加还是减，空间就是 $2m$ 了。

算出的答案变化量实际上对后续操作有影响，所以要做前缀和。

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// luogu_4887
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define cnt(x) __builtin_popcount(x)
#define pb push_back
using namespace std;

typedef long long ll;
const int N = 1e5 + 5, V = 16390;
int n, m, K, unit;
int a[N], bin[V];
ll ans[N], pre[N];
struct Ques { int l, r, id; ll ans; } q[N];
struct atom {
    int l, r, id, op;
    atom(int L, int R, int Id, int Op) { l = L, r = R, id = Id, op = Op; }
};
vector<int> buc;
vector<atom> vec[N];

bool cmp(Ques a, Ques b) {
    return a.l / unit == b.l / unit ? a.r < b.r : a.l < b.l;
}

int main() {
    cin >> n >> m >> K;
    if (K > 14) {
        rep(i, 1, m) puts("0"); return 0;
    }
    unit = n / sqrt(m);
    rep(i, 1, n) {
        scanf("%d", &a[i]);
    }
    rep(i, 1, m) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    rep(i, 0, 16383)
        if (cnt(i) == K) buc.pb(i);
    rep(i, 1, n) {
        pre[i] = bin[a[i]] + pre[i - 1];
        for (int j = 0; j < buc.size(); j++) ++bin[a[i] ^ buc[j]];
    }
    int L = 1, R = 0;
    rep(i, 1, m) {
        int l = q[i].l, r = q[i].r;
        ll &x = q[i].ans;
        if (L > l)
            vec[R].pb(atom(l, L - 1, i, 1)), x -= pre[L - 1] - pre[l - 1], L = l;
        // while (L > l)
        //     --L, x -= pre[L];
        if (R < r)
            vec[L - 1].pb(atom(R + 1, r, i, -1)), x += pre[r] - pre[R], R = r;
        // while (R < r)
        //     ++R, x += pre[R];
        if (L < l)
            vec[R].pb(atom(L, l - 1, i, -1)), x += pre[l - 1] - pre[L - 1], L = l;
        // while (L < l)
        //     x += pre[L], ++L;
        if (R > r)
            vec[L - 1].pb(atom(r + 1, R, i, 1)), x -= pre[R] - pre[r], R = r;
        // while (R > r)
        //     x -= pre[R], --R;
    }
    memset(bin, 0, sizeof(bin));
    rep(i, 1, n) {
        for (int j = 0; j < buc.size(); j++) ++bin[a[i] ^ buc[j]];
        for (int j = 0; j < vec[i].size(); j++) {
            atom t = vec[i][j];
            rep(k, t.l, t.r) {
                if (k <= i && !K) q[t.id].ans += t.op * (bin[a[k]] - 1);
                else q[t.id].ans += t.op * bin[a[k]];
            }
        }
    }
    rep(i, 1, m) q[i].ans += q[i - 1].ans;
    rep(i, 1, m) ans[q[i].id] = q[i].ans;
    rep(i, 1, m) printf("%lld\n", ans[i]);
    return 0;
}