概述
解决的问题
无修改的离线区间询问问题
对问题的要求
假设 $n$ 为下标范围,$m$ 为询问次数,若从 $[l, r]$ 的答案能够以某种方式(假设一次转移的复杂度为$\Theta(x)$)扩展到 $[l - 1, r], [l + 1, r], [l, r + 1], [l, r - 1]$的答案,那么所有询问可以使用莫队算法在 $\Theta((n + m) \sqrt{n} \cdot x)$ 的时间内求出
实现
简易版本
流程
- 离线后排序(左端点 $l$ 为第一关键字,右端点 $r$ 为第二关键字)
- 设置初始位置:$l = 1, r = 0, now = 0 (now为当前答案)$
- 顺序处理每个询问
代码
注:此代码以统计区间不同数字个数为例
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
| struct Query {
int l, r;
int id, ans;
};
int n, m;
int a[MAXN];
Query q[MAXQ];
int cnt[MAXN];
int l, r, ans;
bool cmpRG(const Query &_a, const Query &_b) { // 左端点为第一关键字,右端点为第二关键字
if(_a.l != _b.l) {
return _a.l < _b.l;
} else {
return _a.r < _b.r;
}
}
bool cmpID(const Query &_a, const Query &_b) { // id
return _a.id < _b.id;
}
void add(int x) { // 向区间添加元素,更新当前答案
cnt[a[x]]++;
if(cnt[a[x]] == 1) {
ans++;
}
}
void del(int x) { // 从区间删除元素,更新答案
cnt[a[x]]--;
if(cnt[a[x]] == 0) {
ans--;
}
}
int main() {
// Code here...
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1, cmpRG); // 对区间排序
l = 1; // 初始位置
r = 0;
ans = 0;
for(int i = 1; i <= m; i++) {
while(r > q[i].r) { // 移动到新区间
del(r--);
}
while(r < q[i].r) {
add(++r);
}
while(l > q[i].l) {
add(--l);
}
while(l < q[i].l) {
del(l++);
}
q[i].ans = ans;
}
sort(q + 1, q + m + 1, cmpID); // 恢复原顺序
// Code here...
}
|
优化
过程
可以发现,在最劣的情况下,比如询问的区间为 $[1, 1], [1, 50], [1, 100], [2, 2], [2, 50], [2, 100], [3, 3], [3, 50], [3, 100]$ 时,左端点只会移动 $3$ 次,但是右端点会移动大约 $300$ 次
但是,如果对其按如下方式排序,移动次数就会大大降低
$$
[1, 1], [2, 2], [3, 3], [1, 50], [2, 50], [3, 50], [1, 100], [2, 100], [3, 100]
$$
此时左端点大约会移动 $10$ 次,而右端点则会移动 $100$ 次
这只是一个极端情况,对于普遍的情况,莫涛大神则提出了一种基于分块的方法:
- 将下标范围 $[1, n]$ 分为 $\sqrt{n}$ 块($[1, \sqrt{n}], [\sqrt{n} + 1, 2\sqrt{n}] \dots$)
- 以区间左端点所在的块的编号为第一关键字,以右端点为第二关键字对所有询问区间排序
- 设置初始位置并顺序处理每个询问(同上)
这样,对于每一个块中的询问(此处询问所在的块即指询问左端点所在的块),右端点的移动范围都是 $n$(因为同一块内询问右端点有序,最多只会从下标 $1$ 移到下标 $n$),所以右端点移动的总复杂度为 $\Theta(n\sqrt{n})$(总共有 $\sqrt{n}$ 个块);而对于左端点,如果在块内移动,那么范围就是 $\sqrt{n}$,如果在块间移动,那么范围至多也不超过 $\Theta(2\sqrt{n})$(移动到下一个区间),所以左端点移动的总复杂度为 $\Theta(m\sqrt{n})$(每次移动都是 $\Theta{\sqrt{n}}$)
所以,算法总复杂度为 $\Theta((n + m) \sqrt{n})$,如果算上每次移动的复杂度为 $\Theta(x)$,则总复杂度为 $\Theta((n + m) \sqrt{n} \cdot 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
| struct Query {
int l, r;
int id, ans;
};
int n, m;
int a[MAXN];
Query q[MAXQ];
int cnt[MAXN];
int l, r, ans;
int block;
bool cmpRG(const Query &_a, const Query &_b) { // 左端点为第一关键字,右端点为第二关键字
if(_a.l / block != _b.l / block) {
return _a.l < _b.l;
} else {
return _a.r < _b.r;
}
}
bool cmpID(const Query &_a, const Query &_b) { // id
return _a.id < _b.id;
}
void add(int x) { // 向区间添加元素,更新当前答案
cnt[a[x]]++;
if(cnt[a[x]] == 1) {
ans++;
}
}
void del(int x) { // 从区间删除元素,更新答案
cnt[a[x]]--;
if(cnt[a[x]] == 0) {
ans--;
}
}
int main() {
// Code here...
block = sqrt(n);
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1, cmpRG); // 对区间排序
l = 1; // 初始位置
r = 0;
ans = 0;
for(int i = 1; i <= m; i++) {
while(r > q[i].r) { // 移动到新区间
del(r--);
}
while(r < q[i].r) {
add(++r);
}
while(l > q[i].l) {
add(--l);
}
while(l < q[i].l) {
del(l++);
}
q[i].ans = ans;
}
sort(q + 1, q + m + 1, cmpID); // 恢复原顺序
// Code here...
}
|
再优化(蛇形移动)
可以发现,每次从一个块前往下一个块的时候,左端点常常会移动很远,此时,我们可以利用蛇形移动来优化。
我们先将左端点和右端点在坐标系中形象地表示出来:
所谓蛇形移动,就是对于奇数块和偶数块在块内采用相反的方向按右端点排序。这样,每次解决完一个块时,我们不必使左端点回到头部,所以可以节省部分时间。
当然,这种方法通常是常数级优化。
具体实现
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
| struct Query {
int l, r;
int lid; // 左端点所在的块的编号
int id, ans;
};
int n, m;
int a[MAXN];
Query q[MAXQ];
int cnt[MAXN];
int l, r, ans;
int block;
bool cmpRG(const Query &_a, const Query &_b) { // 左端点为第一关键字,右端点为第二关键字
if(_a.lid != _b.lid) {
return _a.lid < _b.lid;
} else {
if(_a.lid % 2) { // 奇数块
return _a.r < _b.r; // 升序排列
} else { // 偶数块
return _a.r > _b.r; // 降序排列
}
}
}
bool cmpID(const Query &_a, const Query &_b) { // id
return _a.id < _b.id;
}
void add(int x) { // 向区间添加元素,更新当前答案
cnt[a[x]]++;
if(cnt[a[x]] == 1) {
ans++;
}
}
void del(int x) { // 从区间删除元素,更新答案
cnt[a[x]]--;
if(cnt[a[x]] == 0) {
ans--;
}
}
int main() {
// Code here...
block = sqrt(n);
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].lid = q[i].l / block;
q[i].id = i;
}
sort(q + 1, q + m + 1, cmpRG); // 对区间排序
l = 1; // 初始位置
r = 0;
ans = 0;
for(int i = 1; i <= m; i++) {
while(r > q[i].r) { // 移动到新区间
del(r--);
}
while(r < q[i].r) {
add(++r);
}
while(l > q[i].l) {
add(--l);
}
while(l < q[i].l) {
del(l++);
}
q[i].ans = ans;
}
sort(q + 1, q + m + 1, cmpID); // 恢复原顺序
// Code here...
}
|