分块,然后捡到莫队

前言

HDU多校连续两天都遇到了莫队的题,于是蒟蒻缓慢地开始学习莫队算法

初见莫队,只知道是个离线区间工具,以为会有点复杂。但其实基础的莫队很好理解,就是一种读完之后感觉很普通的离线的分块算法(虽然,我还是不可能想得到就是了

分块算法

为了引入莫队,不妨先看一个分块的经典例题(不想看可以通过目录跳过)

洛谷P3870 开关

简化题意:一个01序列,要求可以进行动态区间取反和区间查询(有几个1)。

序列和询问的数据规模都是$1e5$,暴力遍历区间的复杂度是$O(nm)$,显然无法接受。

考虑分块,将长度为$n$的序列切割成$\sqrt n$个固定的区间,每个区间长度$\sqrt n$. 那么我们设想,对于每次询问/修改,我们直接维护区间的状态就好了,对各个分块维护一个$ans$数组,由于区间最多$\sqrt n$个,所以复杂度就会降到$O(m\sqrt n)$.

但是很快就发现,每次询问和修改不一定都恰好落在我们分好的区间边界上。例如,我们的划分是$(1,3),(4,6),(7,10)$,但某次询问的操作区间是$(2,9)$,那么,就会有$(2,3)$和$(7,9)$这两个我们没有划出来的区间。

怎么办?暴力计算!由于每个区间的长度最多$\sqrt n$,因此当询问区间的起始区间和结尾区间不完整时,我们大可以对这两个区间暴力维护答案。因此最终的复杂度仍然是$O(m\sqrt n)$.

有的人可能会问:为什么分块的长度要是 $\sqrt n$ 呢?

不妨分析:假设分块的长度是$x$,那么块的数量就是$n/x$. 每次询问过程中,我们都需要处理开头区间,结尾区间,以及在中间的剩下的完整的区间。这些完整的区间操作都是$O(1)$的,而他们的数量规模导致了这些区间的操作总复杂度在$O(n/x)$. 又我们可能还需要暴力地操作一头一尾,所以我们还需要$O(x)$的时间去完成。那么总时间就会使$O(max(n/x,x))$. 显然,这里$x$取$\sqrt n$可以让每次询问的复杂度最小。

分析完了,现在我们需要考虑,如何具体地进行答案维护与暴力。

由于分块的过程中有部分暴力,对块的操作与对单个元素的操作是并存的。为了让整块操作与散块操作不冲突,我们可以为每个区间打上tag,tag为0表示该区间正常计算,tag为1表示该区间全部取反计算。那么每次整块操作时,我们只需要关心tag,对tag取反即可。而散块操作时,我们不需要关心tag,只需要对每个位置分别取反即可。最后维护出每个块的$ans$.

而在询问时,如果这个区间的tag是0,说明区间没有被整个取反,那么我们直接取其$ans$作为答案;如果tag是1,那么区间被取反,所以我们也要对$ans$取反,以$n-ans$作为答案。

代码(注释详解)

(由于也才没学多久,没看过板子,代码属于自己乱搞,可能有很多冗余繁杂的地方,但应该相对好理解)

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
const int N = 10005, M = 100005;
using namespace std;
struct node{
int l, r, ans, tag;
}a[N];
int st[M] = {0}; // 开灯状态,用于散块暴力
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int n, m; // 灯的数目和操作数目
cin >> n >> m;
int now = 1;
int num = 0;
fors(i, 1, n){
if(now >= n + 1) break;
num++;
a[i].l = now;
a[i].r = min(n, now + (int)sqrt(n));
now = a[i].r + 1;
a[i].ans = a[i].tag = 0; // 开灯数目和tag
} // 分块操作
int p, l, r;
while(m--)
{
cin >> p >> l >> r;
if(p){ // query
int i = 1;
while(i <= num && a[i].l < l) i++;
if(i > num || a[i].l > l) i--;
// 找到左端散区间a[i]
int ans = 0; // 总答案
if(a[i].l != l) // 注意这个if语句避免了把最左边的整块当散块
{
fors(j, l, min(a[i].r, r)){
if(st[j] ^ a[i].tag) ans++;
}
i++;
}
while(i <= num && a[i].r <= r){
ans += a[i].ans;
i++;
}
if(i <= num){
fors(j, a[i].l, r){
if(st[j] ^ a[i].tag) ans++;
}
}
cout << ans << endl;
}
else{ // switch
int i = 1;
while(i <= num && a[i].l < l) i++;
if(i > num || a[i].l > l) i--;
// 找到左端散区间a[i]
int tmp = 0; // 修改后,散区间净增加多少个打开的灯
if(a[i].l != l) // 注意这个if语句避免了把最左边的整块当散块
{
fors(j, l, min(a[i].r, r)){
if(st[j] ^ a[i].tag) tmp--; // 如果区间的tag和其中某点不同,说明灯本来开着,使tmp--
else tmp++; // 否则tmp++
st[j] = 1 - st[j];
}
a[i].ans += tmp;
i++;
}
//-----
while(i <= num && a[i].r <= r){
a[i].ans = a[i].r - a[i].l + 1 - a[i].ans; // 反转ans
a[i].tag = 1 - a[i].tag; // 反转tag
i++;
}
//-----整块修改
if(i <= num){
tmp = 0;
fors(j, a[i].l, r){
if(st[j] ^ a[i].tag) tmp--; // 如果区间的tag和其中某点不同,说明灯本来开着,使tmp--
else tmp++; // 否则tmp++
st[j] = 1 - st[j];
}
a[i].ans += tmp;
}
}
}
return 0;
}

以此,我们了解了分块的基础知识。

普通莫队

实际上,普通莫队可能比上面那题还要好写

例题:

洛谷P2709 小B的询问](https://www.luogu.com.cn/problem/P2709))

需要维护每个数字出现的次数。

考虑将整个序列分成$\sqrt n$块,对每个询问,按照它们$l$(左边界)的位置将这些询问放入不同的块内。例如,$n=9$,分成$(1,3),(4,6),(7,9)$三块,然后询问的区间分别是$(5,7),(1,4),(6,8)$.

那么$(1,4)$在第一块内,$(5,7),(6,8)$在第二块内。

最后维护两个指针$l,r$,通过双指针的移动保存$(l,r)$的答案。

分析复杂度:

在每一块内,$l$最多移动$\sqrt n$次,但$r$就不确定了,每次询问都可能移动$n$次。这样的话就麻烦了,复杂度又回到了$O(nm)$. 如何解决呢?对每一块内的询问,我们将所有询问按$r$升序排序。这样就能保证$r$的移动规模在$O(n)$范围内了。$l$的移动范围很小,只有,所以我们对$r$排序,不对$l$排序。

那么,对于整个序列,$r$的移动也是$O(n)$的,这将与询问次数无关。每次询问,$l$的移动都是$O(\sqrt n)$的,故整个复杂度是$O(m\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
73
74
75
76
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 5e4 + 10;
int n, m, k;
struct query
{
int l, r; ll ans;// 左右边界;询问结果
int idx, blc; // 下标;属于第几个块
}q[maxn];
int st[maxn]; // 原数组
bool cmp1(const query& x, const query& y)
{
if(x.blc != y.blc) return x.blc < y.blc;
return x.r < y.r;
}

bool rearr(const query& x, const query& y){
return x.idx < y.idx;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
cin >> n >> m >> k;
fors(i, 1, n) cin >> st[i];

fors(i, 1, m) cin >> q[i].l >> q[i].r, q[i].idx = i, q[i].blc = (q[i].l - 1) / (int)sqrt(n) + 1;
sort(q + 1, q + 1 + m, cmp1);

ll ans = 0; // 当前答案
unordered_map<int, int> mp; // 存每个数的出现次数
int l = 1, r = 0;
fors(i, 1, m)
{
while(l > q[i].l){
l--;
ans -= mp[st[l]] * mp[st[l]];
mp[st[l]]++;
ans += mp[st[l]] * mp[st[l]];
}
while(r < q[i].r){
r++;
ans -= mp[st[r]] * mp[st[r]];
mp[st[r]]++;
ans += mp[st[r]] * mp[st[r]];
}
while(l < q[i].l){
ans -= mp[st[l]] * mp[st[l]];
mp[st[l]]--;
ans += mp[st[l]] * mp[st[l]];
l++;
}
while(r > q[i].r){
ans -= mp[st[r]] * mp[st[r]];
mp[st[r]]--;
ans += mp[st[r]] * mp[st[r]];
r--;
}
q[i].ans = ans;
}
sort(q + 1, q + 1 + m, rearr);
fors(i, 1, m) cout << q[i].ans << endl;
return 0;
}