本文最后更新于：March 18, 2022 pm

例题

$\texttt{Luogu P4887 [模板]莫队二次离线}$

设莫队指针移动时间复杂度为 $O(k)$ ，则普通莫队的时间复杂度为 $O(m\sqrt n k)$ ，使用莫队二次离线可以变成 $O(m\sqrt n + nk)$ 。

本题直接莫队做是 $O(m\sqrt n\binom{14}{k})$ 的，无法通过。

记 $a_x$ 对区间 $[l,r]$ 的贡献为 $f(x,[l,r])$，差分后贡献记为 $f(x,r)-f(x,l-1)$，即 $f(x,r)$ 表示 $x$ 对前缀 $[1,r]$ 的贡献。考虑莫队指针移动过程中答案的变化：

$[l,r]\longrightarrow [l,qr]:$
- $qr > r:$ 答案增加 $\sum\limits_{i=r+1}^{qr}f(i,i-1)-f(i,l-1)$
- $qr < r:$ 答案减少 $\sum\limits_{i=qr+1}^r f(i,i-1) - f(i,l-1)$
$[l,r]\longrightarrow [ql,r]:$
- $ql < l:$ 答案增加 $\sum\limits_{i=ql}^{l-1} f(i,r)-f(i,i)$
- $ql > l:$ 答案减少 $\sum\limits_{i=l}^{ql-1} f(i,r)-f(i,i)$

$f(i,i)$ 和 $f(i,i-1)$ 都是固定的，可以预处理直接计算；

$f(i,l-1)$ 和 $f(i,r)$ 则使用扫描线解决，具体地说：

对于每个前缀 $[1,i]$，开一个 $vector$ 存下所有的询问 $f([l,r],i)$，记 $g(x)$ 表示 $a_{[1,i]}$ 中 $\oplus x$ 的二进制表示下恰好有 $k$ 个 $1$ 的个数，则对于询问 $f([l,r],i)$ 的贡献即为 $\sum\limits_{i=l}^r g(a_i)$。
处理完 $[1,i]$ 然后处理 $[1,i+1]$ 时，枚举 $a_{i+1}$ 取反 $k$ 位更新 $g$ 即可。

询问可以用四元组 $(l,r,id,1/-1)$ 表示询问 $f([l,r],i)$，询问编号 $id$ 以及增减 $1/-1$。

$\texttt{Code:}$

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
inline int read() {
    int x = 0, f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5;
int n, m, k, a[maxn], B;
struct _ques {
    int l, r, id, pos;
    bool operator < (const _ques &a) const {
        return pos ^ a.pos ? l < a.l : pos & 1 ? r > a.r : r < a.r;
    }
} qr[maxn];
long long sum[maxn], ans[maxn];
int f[maxn], g[maxn];
vector<int> trs;
struct st {
    int l, r, id, dt;
    st (int l = 0, int r = 0, int id = 0, int dt = 0) : l(l), r(r), id(id), dt(dt) {}
};
vector<st> vec[maxn];
int main() {
    n = read(); m = read(); k = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    B = sqrt(n);
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        qr[i] = (_ques){l, r, i, l / B};
    }
    for (int S = 0; S < (1 << 14); S++) {
        int cnt = 0;
        for (int i = 0; i < 14; i++) cnt += S >> i & 1;
        if (cnt == k) trs.pb(S);
    }
    for (int i = 1; i <= n; i++) {
        f[i] = g[a[i]];
        for (auto S : trs) g[a[i] ^ S]++;
    }
    memset(g, 0, sizeof(g));
    sort(qr + 1, qr + m + 1);
    int l = qr[1].l, r = qr[1].r;
    for (int i = l + 1; i <= r; i++) sum[1] += f[i];
    if (l < r) vec[l - 1].pb(st(l + 1, r, 1, -1));
    for (int i = 2; i <= m; i++) {
        if (r < qr[i].r) vec[l - 1].pb(st(r + 1, qr[i].r, i, -1));
        if (r > qr[i].r) vec[l - 1].pb(st(qr[i].r + 1, r, i, 1));
        while (r < qr[i].r) sum[i] += f[++r];
        while (r > qr[i].r) sum[i] -= f[r--];
        if (l > qr[i].l) vec[r].pb(st(qr[i].l, l - 1, i, 1));
        if (l < qr[i].l) vec[r].pb(st(l, qr[i].l - 1, i, -1));
        while (l > qr[i].l) sum[i] -= f[--l];
        while (l < qr[i].l) sum[i] += f[l++];
    }
    for (int i = 1; i <= n; i++) {
        for (auto S : trs) g[a[i] ^ S]++;
        for (st qry : vec[i]) {
            for (int j = qry.l; j <= qry.r; j++) {
                sum[qry.id] += qry.dt * g[a[j]];
                if (j <= i && k == 0) sum[qry.id] -= qry.dt;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        sum[i] += sum[i - 1];
        ans[qr[i].id] = sum[i];
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    return 0;
}

习题

学习笔记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

CF1017G The Tree Previous

群论学习笔记 Next

莫队二次离线学习笔记

例题

习题