学习笔记
本文记录了普通莫队，带修莫队，回滚莫队，树上莫队的学习笔记。
莫队引入
一类区间询问的离线问题：对于一个 $n$ 个数的序列，有 $m$ 次询问，每次询问一个区间 $[l,r]$ 的某种属性。
如果对于某一个区间 $[l,r]$ 的询问的答案，能够 $O(1)$ 的转移到 $[l-1,r]$，$[l+1,r]$，$[l,r-1]$，$[l,r+1]$ 的答案，那么就可以通过莫队算法来优化，莫队算法通过对询问排序，可以把复杂度优化到 $O(n\sqrt{m})$。
基础莫队
思路
首先对序列分块，每块的大小为 $B$，则共有 $n/B$ 块，把询问区间排序，规则为：以区间左端点所处的块编号为第一关键字，区间右端点为第二关键字升序排序。
初始化莫队区间为 $[l,r]=[1,0]$，显然这是一个空的区间，接下来对于每一个询问 $i$，我们要把这个莫队区间，通过移动 $l,r$ 指针调整到询问的区间 $[q[i].l,q[i].r]$，同时维护答案。
分别考虑 $l,r$ 两个指针的总共移动次数。
$r$ 指针
- 某些区间的左端点属于同一块，那么它们的右端点递增，即 $r$ 指针最多走 $n$ 步。一共有 $n/B$ 块，那么 $r$ 总共最多移动了 $n^2/B$ 步。
- 相邻询问左端点不属于同一块，那么右端点移动最多需要移动 $n$ 步，但因为块数只有 $n/B$ 块，因此最多只会有 $n/B$ 个询问达到最坏，因此总共最多移动了 $n^2/B$ 步。（这里很多地方的分析都不一样，我只是按照自己的想法大概思考了一下qwq，有问题请指出）
$l$ 指针
- 如果相邻询问的左端点属于同一块，那么 $l$ 指针只需要在块内移动，最多走 $B$ 步，共有 $m$ 次询问，因此总共最多走 $mB$ 步。
- 如果相邻询问的左端点是跨块的，由于不属于同一个块，那么左端点一定是递增的，那么 $l$ 总共最多向后移动 $n$ 步。
因此 $l,r$ 指针的总复杂度为 $O(n^2/B+mB)$ 。由基本不等式 $n^2/B+mB \ge 2\sqrt{n^2 m}\quad \mathrm{iff}\ B=n / \sqrt{m} $ 。因此取 $B=n/\sqrt{m}$ 时，复杂度为 $O(n\sqrt{m})$ 。'
有一定优化作用的排序方式：奇偶排序，若左端点属于奇数块，则的右端点升序排，左端点属于偶数块中则右端点降序排。
1
2
3
4
5
6
7
| struct Query {
int id, l, r;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return belong[l] & 1 ? r < W.r : r > W.r;
}
} q[N];
|
AcWing2492 HH的项链
题目链接
对于区间 $[l,r]$ 维护 $cnt[\ ]$ 来记录每个数字出现的次数，$res$ 记录当前区间中不同数字出现的次数。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 50010, M = 200010, V = 1000010;
int n, m, B;
int belong[N];
int a[N], cnt[V];
struct Node {
int id, l, r;
bool operator < (const Node &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} query[M];
int ans[M];
void build() {
B = n / sqrt(m);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
void add(int x, int &res) {
if (++cnt[x] == 1) res++;
}
void del(int x, int &res) {
if (--cnt[x] == 0) res--;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
build();
for (int i = 0; i < m; i++) {
int l, r; scanf("%d%d", &l, &r);
query[i] = {i, l, r};
}
sort(query, query + m);
for (int i = 0, l = 1, r = 0, res = 0; i < m; i++) {
while (r < query[i].r) add(a[++r], res);
while (l > query[i].l) add(a[--l], res);
while (r > query[i].r) del(a[r--], res);
while (l < query[i].l) del(a[l++], res);
ans[query[i].id] = res;
}
for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
return 0;
}
|
带修莫队
思路
待修莫队实际上是在基础莫队的情况下，增加了一个时间维度，维护的莫队区间为 $[l,r,ts]$，答案为 $res$，表示当前维护的区间 $[l,r]$ 是在第 $ts$ 次修改之后，第 $ts + 1$ 次修改之前的状态。同样可以从 $[l,r,ts]$ 的答案 $O(1)$ 转移到 $[l-1,r,ts]$，$[l+1,r,ts]$，$[l,r-1,ts]$，$[l,r+1,ts]$，$[l,r,ts-1]$，$[l,r,ts+1]$ 。
分块的块大小为 $B$，共 $n/B$ 块，$m$ 次操作，其中修改操作 $t$ 次，查询 $m-t$ 次。
对于询问的排序规则：以 $\mathrm{belong}[l]$ 为第一关键字，$\mathrm{belong}[r]$ 为第二关键字，$ts$ 为第三关键字升序排序。
初始莫队区间为 $[l,r,ts]=[1,0,0]$，然后我们分别考虑 $l,r,ts$ 指针移动的次数。
$l$ 指针：$O(B(m-t)+n)$
$r$ 指针：$O(B(m-t)+n^2/B)$
$ts$ 指针
- 相邻询问左端点属于同一块，右端点也属于同一块，那么时间戳递增，$ts$ 最多移动 $t$ 步。
- 相邻询问左端点不属于同一块了或者右端点不属于同一块了，那么时间戳不一定有序，所以 $ts$ 最多还是会走 $t$ 步。
- 总结：左右端点所属块编号各有 $n/B$ 种，因此 $ts$ 移动的总复杂度 $O(n^2/B^2\cdot t)$
当 $B=\sqrt[3]{nt}$ 时，复杂度最优为 $O(\sqrt[3]{n^4 t})$，如果 $n,t$ 同阶，则 $B=\sqrt[3]{n^2}$ 时，复杂度最优为 $O(\sqrt[3]{n^5})$ 。
AcWing2521 数颜色
题目链接
时间轴上的 $ts$ 指针移动，需要一点技巧。如果当前莫队区间的时间戳 $ts$ 比查询区间的时间戳 $q[i].ts$ 小的话，需要将 $ts+1\text{~}q[i].ts$ 时刻的修改造成的影响累加到答案上，这点并不难做，反之如果 $ts > q[i].ts$，就需要撤销 $q[i].ts+1\text{~}ts$ 时刻的修改对答案的影响，比较难处理。因此，我们可以沿时间戳增量修改的时候，将已经用到的修改操作中的颜色，与被修改位置的颜色交换，那么下一次需要撤销这次修改时，就等价于再对这个位置进行一次修改操作，而由于之前修改和被修改的颜色进行了交换，因此直接执行这次修改操作恰好是撤销的效果。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 1000010;
int n, m, B;
int color[N], belong[N];
int qcnt, pcnt; // qcnt为询问编号，pcnt为操作的编号
struct Query {
int id, l, r, ts; // id表示当前询问的编号，ts表示当前询问处于第ts次操作后，第ts+1操作前
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
if (belong[r] != belong[W.r]) return belong[r] < belong[W.r];
return ts < W.ts;
}
} q[N];
struct Modify {
int x, c; // 将下标为x的位置的颜色修改成c
} p[N];
int cnt[M], ans[N];
void build() {
B = pow(n, 2.0 / 3);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
void add(int x, int &res) {
if (++cnt[x] == 1) res++;
}
void del(int x, int &res) {
if (--cnt[x] == 0) res--;
}
// 将编号为ts的操作的影响作用到编号为i的询问
void modify(int ts, int i, int &res) {
// 如果第ts次操作的位置在第i次询问的区间内部，就需要删除原来的颜色，再加上新颜色，以对答案造成影响
if (p[ts].x >= q[i].l && p[ts].x <= q[i].r) {
del(color[p[ts].x], res);
add(p[ts].c, res);
}
// 上面只是修改cnt和res，实际的颜色修改，技巧，交换原来的颜色，和第ts次操作的颜色，这样下次需要撤销这次操作，相当于执行这次颜色被交换过的新操作。
swap(color[p[ts].x], p[ts].c);
}
int main() {
scanf("%d%d", &n, &m);
build();
for (int i = 1; i <= n; i++) scanf("%d", &color[i]);
for (int i = 0; i < m; i++) {
char op[2];
int l, r;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q') {
++qcnt;
q[qcnt] = {qcnt, l, r, pcnt}; // 询问
} else {
p[++pcnt] = {l, r}; // 修改
}
}
// 对于询问排序
sort(q + 1, q + qcnt + 1);
// 枚举每一个询问，初始下标区间为[l,r]为[1, 0]，为空，不同颜色个数res=0，处在第ts=0个操作之后，第ts+1=1个操作之前
for (int i = 1, l = 1, r = 0, res = 0, ts = 0; i <= qcnt; i++) {
// 将[l,r,ts]移动到[q[i].l, q[i].r, q[i].ts]
while (r < q[i].r) add(color[++r], res);
while (l > q[i].l) add(color[--l], res);
while (r > q[i].r) del(color[r--], res);
while (l < q[i].l) del(color[l++], res);
while (ts < q[i].ts) modify(++ts, i, res); // 需要将ts+1~q[i].ts的操作造成的影响累加到答案上
while (ts > q[i].ts) modify(ts--, i, res); // 需要消除q[i].ts+1~ts的操作对答案的影响
ans[q[i].id] = res;
}
for (int i = 1; i <= qcnt; i++) printf("%d\n", ans[i]);
return 0;
}
|
回滚莫队
思路
回滚莫队，一般用在当区间维护的答案只具有“可加性”或者只具有“可减性”时，这里只讨论，只具有“可加性”的情况。对于此类情况，回滚莫队能将删除操作 del 全部转化为插入操作 add。
AcWing2523 历史研究
题目链接
首先对原序列分块，然后对询问排序，以区间左端点所在块编号为第一关键字，区间右端点为第二关键字升序排序。
我们依次处理询问，我们对询问进行分段处理，把左端点处于同一块的询问放在一起处理。
对于这些左端点处于同一块的询问来说，它们的右端点递增，我们再细分为两种情况。
左右端点在同一块内：直接暴力做就行了，$l,r$ 指针移动是 $O(n)$ 的。
左右端点跨块：如下图所示 $[q[i].l,q[i].r]$,$[q[i+1].l, q[i+1].r]$ 都是跨块的。
此时我们要处理第 $i$ 个询问，将莫队区间的右端点 $r=r_0$ 初始化为第 $i$ 个询问的左端点所处块的右边界。左端点 $l=l_0=r_0+1$ 。
需要注意的是，我们维护的答案，并不是整个 $[l,r]$ 区间的答案，而是区间 $[l_0,r]$ 的答案。因为查询区间的右端点是递增的，而左端点是无序的，我们又无法使用删除操作，因此，我们每次只维护 $[l_0,r]$ 区间的答案，对于 $l_0$ 左边的部分，采取暴力 add（最多也就一个块的大小的复杂度），来更新答案。
现在我们将 $r$ 指针不断向右扩展，直至 $r$ 指针到达查询区间的右端点 $q[i].r$，然后我们备份此时的答案到 tmp 中，（时刻记得我们维护答案的区间是 $[l_0,r]$）接着让 $l$ 指针不断向左边扩展，直至 $l$ 指针到达查询区间的左端点，此时记录答案即可。可以发现，左右指针都只用了 add 操作。
现在我们考虑这个问题，我们已经处理完了第 $i$ 个询问，接下来如何处理第 $i+1$ 个呢，我们知道这两个询问有共同之处，左端点处于同一块，且询问区间都是跨块的，并且 $q[i].r \le q[i+1].r$，那么就说明我们的 $r$ 指针只需要继续向右 add 即可。对于 $l$ 指针呢，由于我们不能使用删除操作，因此，在第 $i$ 次查询完后，$l$ 必须回到初始位置 $l_0$，也就是回滚，这里我们只需要更改 $cnt[\ ]$ 数组即可，然后把维护的答案更新成备份。
取块大小为 $B=\sqrt{n}$ 的话，总复杂度为 $O(n\sqrt{n}+m\sqrt{n})$ （OI-Wiki）。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m, B, sz;
int belong[N], L[N], R[N], a[N];
struct Query {
int id, l, r;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[N];
vector<int> alls;
int cnt[N];
LL ans[N];
void build() {
B = sqrt(n), sz = (n - 1) / B + 1;
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
for (int i = 1; i <= sz; i++) L[i] = (i - 1) * B + 1, R[i] = L[i] + B - 1;
R[sz] = n;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
void add(int x, LL &res) {
cnt[x]++;
res = max(res, (LL)cnt[x] * alls[x]);
}
int main() {
scanf("%d%d", &n, &m); build();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) a[i] = find(a[i]);
for (int i = 0, l, r; i < m; i++) {
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m);
for (int i = 0; i < m; ) {
int j = i;
while (j + 1 < m && belong[q[i].l] == belong[q[j + 1].l]) j++;
// 此时[i,j]区间内的所有询问的左端点属于同一块，右端点递增
// 暴力求块内（左右端点在同一块内的询问）
while (i <= j && belong[q[i].l] == belong[q[i].r]) {
LL res = 0;
for (int k = q[i].l; k <= q[i].r; k++) add(a[k], res);
ans[q[i].id] = res;
// 清空cnt
for (int k = q[i].l; k <= q[i].r; k++) cnt[a[k]]--;
i++;
}
// 求跨块，分为两部分：左边第一个块内的部分和它右边块的部分
LL res = 0;
int block_id = belong[q[i].l];
int r = R[block_id], l = r + 1; // 莫队区间初始化
// 右端点递增，只存在add操作，左端点先初始化到block_id块的右端点，然后向左使用add操作
while (i <= j) {
while (r < q[i].r) add(a[++r], res);
LL tmp = res; // 备份
while (l > q[i].l) add(a[--l], res);
ans[q[i].id] = res;
// 清空左边部分对于cnt[]的影响，且让l回到初始位置
while (l <= R[belong[q[i].l]]) cnt[a[l++]] -- ;
res = tmp;
i++;
}
// 清空cnt，对于每一块只会执行一次，复杂度为n根号n
memset(cnt, 0, sizeof cnt);
}
for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
return 0;
}
|
树上莫队
思路
一般来说可以通过 $\rm DFS$ 序或者欧拉序将树中节点转化为序列，再用莫队处理。
AcWing2534 树上计数2
题目链接
题意：求树上两点之间的路径上有多少不同的点权。
先求这棵树的欧拉序，$\rm DFS$ 的时候访问点和离开点的时候分别记录该点的编号得到的序列就是欧拉序（每个点都会出现 $2$ 次）。如下图可以观察一下欧拉序和两点之间的路径的关系。
用 $first[i], last[i]$ 分别表示点 $i$ 在欧拉序中第一次出现的位置和最后一次出现的位置。
对于任意两个点 $u,v$，我们首先保证 $first[u] \le first[v]$（即 $u$ 在 $v$ 之前被遍历到）然后讨论 $u,v$ 的两种情况。
$u=lca(u,v)$，那么 $u \rightarrow v$ 的路径上的点就是欧拉序中区间 $[first[u],first[v]]$ 内只出现 $1$ 次的结点。
$u \neq lca(u,v)$，令 $p=lca(u,v)$，那么那么 $u \rightarrow v$ 的路径上的点就是欧拉序中区间 $[last[u],first[v]]$ 内只出现 $1$ 次的结点加上点 $p$ 。
然后莫队搞一下。
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #include <bits/stdc++.h>
using namespace std;
const int N = 40010, M = 100010;
int n, m, B;
int h[N], e[N << 1], ne[N << 1], idx;
int fa[N][16], depth[N];
int que[N], w[N];
int stk[N << 1], top; // 存欧拉序
int first[N], last[N]; // first[i]表示点i在欧拉序中第一次出现的下标
vector<int> alls;
int belong[N << 1];
struct Query {
int id, l, r, p; // [l,r]为查询区间，p不为0表示还需要算上p这个点
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[M];
int cnt[N], ans[M]; // cnt[x]表示权值x出现的次数
bool st[N]; // st[i]=1表示该点（编号i）出现了奇数次，st[i]=0表示（点编号i）出现了偶数次（出现次数只会有0，1，2）
void build(int n) {
B = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs() {
memset(depth, -1, sizeof depth);
int hh = 0, tt = -1;
que[++tt] = 1;
depth[0] = 0, depth[1] = 1; // 1 is root
while (hh <= tt) {
int t = que[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (depth[j] == -1) {
depth[j] = depth[t] + 1;
que[++tt] = j;
fa[j][0] = t;
for (int k = 1; k <= 15; k++) {
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k--) {
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
}
if (a == b) return a;
for (int k = 15; k >= 0; k--) {
if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
}
return fa[a][0];
}
void dfs(int u, int fa) {
stk[++top] = u, first[u] = top;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs(j, u);
}
stk[++top] = u, last[u] = top;
}
void work(int x, int &res) {
st[x] ^= 1;
if (st[x]) { // 编号为x的节点出现了1次，需要加上权值w[x]的一次次数
cnt[w[x]]++;
if (cnt[w[x]] == 1) res++;
} else { // 编号为x的节点出现了2次或0次，需要撤销权值w[x]的一次出现
cnt[w[x]]--;
if (cnt[w[x]] == 0) res--;
}
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
build(n << 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
alls.push_back(w[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) w[i] = find(w[i]);
for (int i = 0; i < n - 1; i++) {
int a, b; scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1, -1); // 求欧拉序
bfs(); // 处理LCA倍增数组
// 构造询问
for (int i = 0; i < m; i++) {
int a, b; scanf("%d%d", &a, &b);
if (first[a] > first[b]) swap(a, b);
int p = lca(a, b);
if (p == a) q[i] = {i, first[a], first[b], 0};
else q[i] = {i, last[a], first[b], p};
}
sort(q, q + m);
// 处理询问
for (int i = 0, l = 1, r = 0, res = 0; i < m; i++) {
while (r > q[i].r) work(stk[r--], res);
while (r < q[i].r) work(stk[++r], res);
while (l > q[i].l) work(stk[--l], res);
while (l < q[i].l) work(stk[l++], res);
if (q[i].p) work(q[i].p, res);
ans[q[i].id] = res;
if (q[i].p) work(q[i].p, res);
}
for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
return 0;
}
|
其他题目
洛谷P1494 [国家集训队]小Z的袜子（基础莫队）
题目链接
对于 $[l,r]$ 区间选出两个颜色一样的袜子的概率即：
$$
\frac{\sum_{\forall x \in a[l\text{~}r]}C_{\mathrm{cnt}[x]}^{2}}{C_{r-l+1}^{2}}
$$
因此我们莫队的区间来维护上式分子的值，每次加入一个数，就把原来的删去，再把新的加上即可，删除一个数同理。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50010;
int n, m;
int a[N], cnt[N];
int belong[N], B;
struct Query {
int id, l, r, a, b;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[N];
int ans[N][2];
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void build() {
B = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
int C(int a, int b = 2) {
return (LL)a * (a - 1) / 2;
}
void add(int x, int &res) {
x = a[x];
cnt[x]++;
res -= C(cnt[x] - 1, 2);
res += C(cnt[x], 2);
}
void del(int x, int &res) {
x = a[x];
cnt[x]--;
res -= C(cnt[x] + 1, 2);
res += C(cnt[x], 2);
}
int main() {
scanf("%d%d", &n, &m); build();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++) {
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m);
int res = 0;
for (int i = 0, l = 1, r = 0; i < m; i++) {
while (r < q[i].r) add(++r, res);
while (l > q[i].l) add(--l, res);
while (r > q[i].r) del(r--, res);
while (l < q[i].l) del(l++, res);
if (q[i].l == q[i].r) {
ans[q[i].id][0] = 0;
ans[q[i].id][1] = 1;
continue;
}
int len = q[i].r - q[i].l + 1;
int g = gcd(res, C(len, 2));
ans[q[i].id][0] = res / g;
ans[q[i].id][1] = C(len, 2) / g;
}
for (int i = 0; i < m; i++) printf("%d/%d\n", ans[i][0], ans[i][1]);
return 0;
}
|
洛谷P4396 [AHOI2013]作业（基础莫队+值域分块）
题目链接
对于每个询问区间 $[l,r]$ 需要求在该区间内值域在 $[a,b]$ 上的数的个数以及不同的数的个数。
可以考虑用两个树状数组来维护当前区间中出现的数字的个数，和不同数字的个数，然后差分一下就得到某个值域中出现的次数了。但这样插入和查询都是 $O(\log n)$ 。加上莫队总复杂度就达到了 $O(n\sqrt{n}\log n)$，这是无法接受的。
考虑值域分块，然后维护每一块的和。插入就是 $O(1)$ 查询为 $O(\sqrt{n})$，不会影响总复杂度。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], cnt[N], s[N][2], sum[N][2];
int belong[N], L[N], R[N], B, sz;
struct Query {
int id, l, r, a, b;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[N];
int ans[N][2];
void build() {
B = sqrt(n), sz = (n - 1) / B + 1;
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
for (int i = 1; i <= sz; i++) L[i] = (i - 1) * B + 1, R[i] = L[i] + B - 1;
R[sz] = n;
}
void add(int x) {
x = a[x];
cnt[x]++;
s[x][0]++, sum[belong[x]][0]++;
if (cnt[x] == 1) s[x][1]++, sum[belong[x]][1]++;
}
void del(int x) {
x = a[x];
cnt[x]--;
s[x][0]--, sum[belong[x]][0]--;
if (cnt[x] == 0) s[x][1]--, sum[belong[x]][1]--;
}
int ask(int l, int r, int type) {
if (belong[l] == belong[r]) {
int res = 0;
for (int i = l; i <= r; i++) res += s[i][type];
return res;
}
int res = 0;
for (int i = l; i <= R[belong[l]]; i++) res += s[i][type];
for (int i = belong[l] + 1; i < belong[r]; i++) res += sum[i][type];
for (int i = L[belong[r]]; i <= r; i++) res += s[i][type];
return res;
}
int main() {
scanf("%d%d", &n, &m); build();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i < m; i++) {
int l, r, a, b;
scanf("%d%d%d%d", &l, &r, &a, &b);
q[i] = {i, l, r, a, b};
}
sort(q, q + m);
for (int i = 0, l = 1, r = 0; i < m; i++) {
while (r < q[i].r) add(++r);
while (l > q[i].l) add(--l);
while (r > q[i].r) del(r--);
while (l < q[i].l) del(l++);
ans[q[i].id][0] = ask(q[i].a, q[i].b, 0);
ans[q[i].id][1] = ask(q[i].a, q[i].b, 1);
}
for (int i = 0; i < m; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
return 0;
}
|
CF220B Little Elephant and Array（基础莫队）
题目链接
每组询问求 $[l, r]$ 区间内 $cnt[x] == x$ 的 $x$ 的个数。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N];
int B, belong[N];
struct Query {
int id, l, r;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[N];
int ans[N];
vector<int> alls;
int cnt[N];
void build() {
B = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
void add(int x, int &res) {
x = a[x];
cnt[x]++;
if (cnt[x] == alls[x]) res++;
else if (cnt[x] - 1 == alls[x]) res--;
}
void del(int x, int &res) {
x = a[x];
cnt[x]--;
if (cnt[x] == alls[x]) res++;
else if (cnt[x] + 1 == alls[x]) res--;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
int main() {
cin >> n >> m; build();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) a[i] = find(a[i]);
for (int i = 0; i < m; i++) {
int l, r; scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m);
for (int i = 0, l = 1, r = 0, res = 0; i < m; i++) {
while (r < q[i].r) add(++r, res);
while (l > q[i].l) add(--l, res);
while (r > q[i].r) del(r--, res);
while (l < q[i].l) del(l++, res);
ans[q[i].id] = res;
}
for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
return 0;
}
|
CF940F Machine Learning（带修莫队）
题目链接
$cnt[x]$ 维护 $[l,r]$ 区间数值 $x$ 出现的次数，$num[x]$ 维护 $cnt=x$ 的出现次数。
求解 mex 时暴力扫描 $num[\ ]$ 即可，找到第一个不为 $0$ 的位置的下标就是答案，每次 mex 操作复杂度为 $O(\sqrt{n})$，总复杂度 $O(n^{\frac{5}{3}}+m\sqrt{n})$ 。
注意点：$4$ 个 while 循环的位置不能随便修改，原先我一直都是随便写的，这次在这个题RE了很多次，翻到 OI-Wiki 莫队中关于四个循环位置的讨论 才找到原因。
大概可以这么记忆，每次写完将两个 add 所属的 while 循环放前面，两个 del 所属的 while 放后面，一定是一种正确的做法。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int a[N];
int B, belong[N];
struct Query {
int id, l, r, ts;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
else if (belong[r] != belong[W.r]) return belong[r] < belong[W.r];
return ts < W.ts;
}
} q[N];
struct Modify {
int x, y;
} p[N];
int pcnt, qcnt;
int ans[N];
vector<int> alls;
int cnt[N], num[N];
void build(int n) {
B = pow(n, 2.0 / 3);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
void add(int x) {
cnt[x]++;
num[cnt[x] - 1]--;
num[cnt[x]]++;
}
void del(int x) {
cnt[x]--;
num[cnt[x] + 1]--;
num[cnt[x]]++;
}
void modify(int ts, int i) {
if (p[ts].x >= q[i].l && p[ts].x <= q[i].r) {
del(a[p[ts].x]);
add(p[ts].y);
}
swap(a[p[ts].x], p[ts].y);
}
int solve() {
int idx = 1;
while (num[idx]) idx++;
return idx;
}
int main() {
scanf("%d%d", &n, &m); build(n << 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
for (int i = 0; i < m; i++) {
int type, l, r;
scanf("%d%d%d", &type, &l, &r);
if (type == 1) {
qcnt++;
q[qcnt] = {qcnt, l, r, pcnt};
} else {
p[++pcnt] = {l, r};
alls.push_back(r);
}
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) a[i] = find(a[i]);
for (int i = 1; i <= pcnt; i++) p[i].y = find(p[i].y);
sort(q + 1, q + qcnt + 1);
for (int i = 1, l = 1, r = 0, ts = 0; i <= qcnt; i++) {
while (l > q[i].l) add(a[--l]);
while (r < q[i].r) add(a[++r]);
while (r > q[i].r) del(a[r--]);
while (l < q[i].l) del(a[l++]);
while (ts > q[i].ts) modify(ts--, i);
while (ts < q[i].ts) modify(++ts, i);
ans[q[i].id] = solve();
}
for (int i = 1; i <= qcnt; i++) printf("%d\n", ans[i]);
return 0;
}
|
CF617E XOR and Favorite Number（基础莫队）
题目链接
$s[i]$ 维护 $a[i]$ 的异或前缀和。每次查询 $[l,r]$ 区间中有多少对 $(i,j)$ 满足 $a[i]\oplus \cdots \oplus a[j]=k$ 即 $s[j]\oplus s[i-1]=k$，即 $[l-1,r]$ 区间中有多少对 $(i,j)$ 满足 $s[j]\oplus s[i]=k$。用 $cnt[\ ]$ 维护区间 $[l-1,r]$ 中前缀异或和 $s[i]$ 出现的次数，那么我们每次加入一个下标为 $x$ 的数 $s[x]$，就只要找到值为 $s[x]\oplus k$ 出现的次数，就是新增的配对数，删去一个点同理。
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m, k;
int a[N];
LL s[N], ans[N];
int B, belong[N];
struct Query {
int id, l, r;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return r < W.r;
}
} q[N];
int cnt[N * 20];
void build() {
B = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
void add(int x, LL &res) {
res += cnt[s[x] ^ k];
cnt[s[x]]++;
}
void del(int x, LL &res) {
cnt[s[x]]--;
res -= cnt[s[x] ^ k];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
build();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] ^ a[i];
}
for (int i = 0; i < m; i++) {
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l - 1, r};
}
sort(q, q + m);
LL res = 0;
for (int i = 0, l = 1, r = 0; i < m; i++) {
while (r < q[i].r) add(++r, res);
while (l > q[i].l) add(--l, res);
while (r > q[i].r) del(r--, res);
while (l < q[i].l) del(l++, res);
ans[q[i].id] = res;
}
for (int i = 0; i < m; i++) printf("%lld\n", ans[i]);
return 0;
}
|
AcWing2525 区间内逆序对数量（二次离线莫队）
每次求解一个区间内的逆序对数量。考虑每次加入或删掉一个数对上一次的区间的影响，可以用树状数组来统计上一个区间内大于或小于某个数的个数，从而计算答案的变化量。但共有 $O(n\sqrt{n})$ 次修改，每次修改的复杂度为 $O(\log n)$ 。会 TLE 。
二次离线后，用分块来维护，就可以 $O(1)$ 修改，$O(\sqrt{n})$ 查询。
qwq树状数组（TLE） $O(n\sqrt{n}\log n)$
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N];
int B, belong[N];
struct Query {
int id, l, r;
bool operator < (const Query &W) const {
if (belong[l] != belong[W.l]) return belong[l] < belong[W.l];
return belong[l] & 1 ? r < W.r : r > W.r;
}
} q[N];
vector<int> alls;
int c[N], ans[N];
int lowbit(int x) {
return x & -x;
}
void ins(int x, int y) {
for (int i = x; i < N; i += lowbit(i)) c[i] += y;
}
int ask(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += c[i];
return res;
}
int find(int x) {
return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
void build() {
B = sqrt(n);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
// type=1表示在右边add, -1表示在左边add
void add(int x, int &res, int type) {
if (type == 1) res += ask(N - 1) - ask(x);
else res += ask(x - 1);
ins(x, 1);
}
// type=1表示在右边删
void del(int x, int &res, int type) {
if (type == 1) res -= ask(N - 1) - ask(x);
else res -= ask(x - 1);
ins(x, -1);
}
int main() {
scanf("%d%d", &n, &m);
build();
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
alls.push_back(a[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i++) a[i] = find(a[i]);
for (int i = 0; i < m; i++) {
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m);
for (int i = 0, l = 1, r = 0, res = 0; i < m; i++) {
while (r < q[i].r) add(a[++r], res, 1);
while (l > q[i].l) add(a[--l], res, -1);
while (r > q[i].r) del(a[r--], res, 1);
while (l < q[i].l) del(a[l++], res, -1);
ans[q[i].id] = res;
}
for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
return 0;
}
|
二次离线莫队的做法还没调出来qwq。
学习资料
- AcWing算法进阶课
- OI-Wiki
- ouuan的博客
- WAMonster的博客
