分块，然后捡到莫队
前言
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 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;
}
int p, l, r;
while(m--)
{
cin >> p >> l >> r;
if(p){
int i = 1;
while(i <= num && a[i].l < l) i++;
if(i > num || a[i].l > l) i--;
int ans = 0;
if(a[i].l != l)
{
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{
int i = 1;
while(i <= num && a[i].l < l) i++;
if(i > num || a[i].l > l) i--;
int tmp = 0;
if(a[i].l != l)
{
fors(j, l, min(a[i].r, r)){
if(st[j] ^ a[i].tag) tmp--;
else 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;
a[i].tag = 1 - a[i].tag;
i++;
}
if(i <= num){
tmp = 0;
fors(j, a[i].l, r){
if(st[j] ^ a[i].tag) tmp--;
else 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)
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
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;
}
|
