Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

二次离线莫队模板

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 3 分钟
标签：    

解决一些一次离线不能完成的问题。

求区间中有多少个二元组异或和中有 $k$ 个 $1$ 。

对于一般的莫队，指针移动一个位置后答案的影响需要 $O(n)$ 计算。考虑将计算过程离线下来。做前缀和表示 $[1 \ldots i]$ 和 $x$ 对答案的贡献。例如当前指针 $r$ 在询问的右边，那么每移动一个，答案需要减少 $[l, r - 1]$ 与 $r$ 的贡献，用前缀和处理后，需要分别计算 $[1, r - 1]$ 和 $[1, l - 1]$ 与 $r$ 的贡献，其中前者可以提前预处理，后者不好算。我们将所有的相同的形如后者的贡献记录下来，后面再计算。而莫队中所有的答案都是再上一个询问的基础上更改，所有最后需要做前缀和。

查看代码 
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, M = 2e4 + 10;
int n, m, k, len, w[N], f[N], g[M];
LL ans[N];
struct Query
{
    LL res;
    int id, l, r;
    friend bool operator<(const Query &x, const Query &y)
    {
        return x.l / len == y.l / len ? x.r < y.r : x.l < y.l;
    }
} q[N];
struct Range
{
    int id, l, r, op;
};
vector<Range> range[N];
int count(int x)
{
    int res = 0;
    while (x)
        res++, x -= x & -x;
    return res;
}
int main()
{
    read(n), read(m), read(k);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    vector<int> nums;
    for (int i = 0; i < (1 << 14); i++)
        count(i) == k && (nums.push_back(i), 0);
    for (int i = 1; i <= n; i++)
    {
        for (int j : nums)
            g[w[i] ^ j]++;
        f[i] = g[w[i + 1]];
    }
    for (int i = 0; i < m; i++)
    {
        read(q[i].l), read(q[i].r);
        q[i].id = i;
    }
    len = max(1, (int)(n / sqrt(m)));
    sort(q, q + m);
    for (int i = 0, l = 1, r = 0; i < m; i++)
    {
        r < q[i].r && (range[l - 1].push_back((Range){i, r + 1, q[i].r, -1}), 0);
        while (r < q[i].r)
            r++, q[i].res += f[r - 1];
        r > q[i].r && (range[l - 1].push_back((Range){i, q[i].r + 1, r, 1}), 0);
        while (r > q[i].r)
            q[i].res -= f[r - 1], r--;
        l < q[i].l && (range[r].push_back((Range){i, l, q[i].l - 1, -1}), 0);
        while (l < q[i].l)
            q[i].res += f[l - 1] + !k, l++;
        l > q[i].l && (range[r].push_back((Range){i, q[i].l, l - 1, 1}), 0);
        while (l > q[i].l)
            l--, q[i].res -= f[l - 1] + !k;
    }
    for (int i = 0; i < (1 << 14); i++)
        g[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j : nums)
            g[w[i] ^ j]++;
        for (Range r : range[i])
            for (int j = r.l; j <= r.r; j++)
                q[r.id].res += g[w[j]] * r.op;
    }
    for (int i = 1; i < m; i++)
        q[i].res += q[i - 1].res;
    for (int i = 0; i < m; i++)
        ans[q[i].id] = q[i].res;
    for (int i = 0; i < m; i++)
        write(ans[i]), puts("");
    return 0;
}