前言
莫队，可是传说中能够解决所有离线区间问题的神奇算法
引子
我们先来看这样一道题：
有一个包含了$n$个数的序列$a_i$
有$m$次询问，每次询问$[l,r]$区间中有多少个不同的数
$n,m \leq 5*10^4$
你会怎么做？暴力？
暴力复杂度是$O(nm)$的，会$T$
1
2
3
4
5
6
7
8
9
10
11
12
13
| for(int i = 1; i <= m; i++)
{
int ans = 0;
memset(cnt, 0, sizeof(cnt));
for(int j = l[i]; j <= r[i]; j++)
{
++cnt[a[i]];
if(cnt[a[i]] == 1)
++ans;
}
printf("%d\n", ans);
}
|
我们来观察一下暴力：
暴力每次询问$[l_i,r_i]$时上一次询问的$[l_{i-1},r_{i-1}]$所存储下来的信息就都被抛弃了
如果我们把上一次查询存储下来的信息再利用呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int l = 1, r = 0, sum = 0;
for (int i = 1; i <= m; i++)
{
while (l > q[i].l)
l--, cnt[a[l]]++, sum += ((cnt[a[l]] == 1) ? 1 : 0);
while (r < q[i].r)
r++, cnt[a[r]]++, sum += ((cnt[a[r]] == 1) ? 1 : 0);
while (l < q[i].l)
cnt[a[l]]--, sum -= ((cnt[a[l]] == 0) ? 1 : 0), l++;
while (r > q[i].r)
cnt[a[r]]--, sum -= ((cnt[a[r]] == 0) ? 1 : 0), r--;
printf("%d\n", sum);
}
|
很不幸，这样写还是会$T$.出题人可以构造数据使你相邻两次查询没有相交项，然后这就成了一个比暴力还劣的算法
但是我们已经离真正的莫队很近了
我们可以把询问分块，把询问依照左端点分成$O(\sqrt n)$块,块内再按右端点排序。
这样子算法的总复杂度就是$O(n \sqrt n)$的
但是，这个复杂度要怎么证明呢？
莫队的复杂度分析
块内转移
在同一个块里面，由于左端点都在一个长度为$O(\sqrt n)$的区间里面
所以在同一块里面移动一次，左端点最多变化$O(\sqrt n)$
总共有$m$个询问，那么同一个块里面的左端点变化最多是$O(m\sqrt n)$的
由于每个块里面的询问都按右端点排序
所以右端点在一个块里面最多变化$n$
有 $\sqrt n$个块，那么右端点移动最多就是$O(n\sqrt n)$
跨块转移
容易发现这样的转移总共会发生$\sqrt n$次
单次跨块转移的复杂度为$O(\sqrt n)$,总复杂度为$O(\sqrt n * \sqrt n)=O(n)$
由于跨块时，右端点是无序的，所以在最坏情况下右端点单次转移的复杂度为$O(n)$,总复杂度为$O(n * \sqrt n)=O(n \sqrt n)$
综上所述，莫队算法的复杂度是$O(n\sqrt n)$(由于$m$与$n$在同一个数量级，所以统一一下就成了$O(n\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
| #include <bits/stdc++.h>
#define ll long long
const int MaxN = 500010;
struct query
{
int l, r, id, pos;
bool operator<(const query &x) const
{
if (pos == x.pos)
return r < x.r;
else
return pos < x.pos;
}
};
query q[MaxN];
int a[MaxN], n, m, k;
int cnt[MaxN << 1], ans[MaxN];
inline int read()
{
int x = 0;
char ch = getchar();
while(ch > '9' || ch < '0')
ch = getchar();
while(ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
int main()
{
n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
m = read();
int size = (int)pow(n, 0.55);
for (int i = 1; i <= m; i++)
{
q[i].l = read(), q[i].r = read();
q[i].id = i, q[i].pos = (q[i].l - 1) / size + 1;
}
std::sort(q + 1, q + m + 1);
int l = 1, r = 0, sum = 0;
for (int i = 1; i <= m; i++)
{
while (l > q[i].l)
l--, cnt[a[l]]++, sum += ((cnt[a[l]] == 1) ? 1 : 0);
while (r < q[i].r)
r++, cnt[a[r]]++, sum += ((cnt[a[r]] == 1) ? 1 : 0);
while (l < q[i].l)
cnt[a[l]]--, sum -= ((cnt[a[l]] == 0) ? 1 : 0), l++;
while (r > q[i].r)
cnt[a[r]]--, sum -= ((cnt[a[r]] == 0) ? 1 : 0), r--;
ans[q[i].id] = sum;
}
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
|
习题
- P2709 小B的询问
普通莫队模板题，建议初学者从这道题入手
- P1972 [SDOI2009]HH的项链
普通莫队模板题，建议初学者从这道题入手
- P3901 数列找不同
可以转化成莫队来做
- P1494 [国家集训队]小Z的袜子
普通莫队模板题
- P4137 Rmq Problem / mex
普通莫队模板题，修改有一些思维难度
- CF375D Tree and Queries
树上问题转区间问题，可以用莫队解决
- SP3267 DQUERY - D-query
HH的项链数据弱化版
- P4396 [AHOI2013]作业
莫队套分块
- P4867 Gty的二逼妹子序列
莫队套分块，是上题第二小问的数据加强版
- P3709 大爷的字符串题
区间众数模板题，不要求在线
带修莫队
留坑待填
树上莫队
留坑待填