分块莫队学习笔记

优雅的暴力。

引入

link。

这道题显然可以用线段树、树状数组做，但如果我偏不用这些数据结构呢？

我们知道，暴力修改和查询最坏是 (mathcal{O}(n)) 的，这样肯定会挂掉。

那该怎么办呢？

正题

分块

考虑将序列分成若干块，我们设每块长为 (B)。

对于每次查询 (left [ l, r right ])，我们涉及到修改的块是 (left [ b_l, b_r right ])（(b_i) 代表 (i) 属于哪个块）。

其中 (left [ b_l + 1, b_r - 1 right ]) 是整块都被修改了。

不妨设置一个懒标记，把每块的整块操作都加到这里面。

这样修改的复杂度是 (mathcal{O}(frac{n}{B})) 的。

那剩下的我们就可以暴力操作，复杂度是 (mathcal{O}(B)) 的。

查询同理。

此时修改查询的复杂度就变成了 (mathcal{O}(B + frac{n}{B})) 了。

使得该数最小的显然是 (B = sqrt{n})，所以该算法的时间复杂度是 (mathcal{O}(msqrt{n}))。

分块主要解决区修区查类问题，只要满足以下条件即可：

• 可以打懒标记（结合律）。
• 时间复杂度允许。

优势：可解决问题范围广。

劣势：时间复杂度高。

时间复杂度：(mathcal{O}(msqrt{n}))。

空间复杂度：(mathcal{O}(n))。

莫队

普通莫队

莫队是一种离线算法，需要满足以下条件：

• 在知道 (left [ l, r right ]) 的答案的情况下，可以 (mathcal{O}(1)) 求出 (left [ l, r + 1 right ])、 (left [ l, r - 1 right ])、 (left [ l + 1, r right ])、 (left [ l - 1, r right ]) 的答案。
• 允许离线。
• 只有询问没有修改。

首先将所有的询问离线下来，记为 (left [ ql_1, qr_1 right ],left [ ql_2, qr_2 right ],dots,left [ ql_m, qr_m right ])。

将询问排序（这正是莫队算法的精髓），从上一个询问的答案一个个改到当前询问，得到答案。

实现：

for (int i = 1; i <= m; i++) { 	while (l < q[i].l) del(l++); 	while (r > q[i].r) del(r--); 	while (l > q[i].l) add(--l); 	while (r < q[i].r) add(++r); 	ans[q[i].id] = res; } 

但是仔细分析发现时间复杂度仍然可以被卡成 (nm)，一点都不优秀，甚至会更慢。

考虑优化。

我们想要优化复杂度的根本是让 (l) 和 (r) 指针移动的距离尽量少。

对询问范围进行分块，块长为 (B)。

以询问左端点的块编号为第一关键字，右端点为第二关键字排序。

• 如果当前询问与上一次处于同一块，则 (l) 最多移动 (B)。
• 不同块的询问，(l) 最多移动 (2B)。

则：

• (l) 移动的复杂度是 (mtimes B = mB)；
• (r) 的复杂度是 (frac{n}{B} times n = frac{n^2}{B})。

则复杂度是 (mathcal{O}(mB + frac{n^2}{B}))。

使得该式最小的 (B) 的值是 (frac{n}{sqrt m})，则此时的时间复杂度就是 (mathcal{O}(nsqrt{m} + mlog m))。

(m log m) 是排序的复杂度。

总结一下。

普通莫队解决的问题满足以下条件：

• 在知道 (left [ l, r right ]) 的答案的情况下，可以 (mathcal{O}(1)) 求出 (left [ l, r + 1 right ])、 (left [ l, r - 1 right ])、 (left [ l + 1, r right ])、 (left [ l - 1, r right ]) 的答案。
• 允许离线。
• 只有询问没有修改。

优势：再没有更快的思维做法之前，她几乎是跑得最快并且思维含量最低的。

劣势：只支持离线。

时间复杂度： (mathcal{O}(nsqrt{m} + mlog m))。

空间复杂度： (mathcal{O}(n))。

例题 1：小 B 的询问

非常板子的一道，维护一下 (c) 数组即可。

#include <bits/stdc++.h> // #define int long long #define pii pair<int, int> #define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout) #define ALL(x) x.begin(), x.end() using namespace std;  int _test_ = 1;  const int N = 50008;  int n, m, k, block_size, res, cnt[N], a[N], ans[N]; struct node { 	int l, r, id; } q[N];  bool operator<(node x, node y) { 	int xl = (x.l - 1) / block_size + 1, xr = (x.r - 1) / block_size + 1; 	int yl = (y.l - 1) / block_size + 1, yr = (y.r - 1) / block_size + 1; 	return (xl != yl) ? (xl < yl) : (x.r < y.r); }  void add(int x) { 	res += cnt[a[x]] * 2 + 1; 	cnt[a[x]]++; }  void del(int x) { 	res -= cnt[a[x]] * 2 - 1; 	cnt[a[x]]--; }  void init() {}  void clear() {}  void solve() { 	cin >> n >> m >> k; 	for (int i = 1; i <= n; i++) { 		cin >> a[i]; 	} 	block_size = n / sqrt(m); // 块长 	for (int i = 1; i <= m; i++) { 		cin >> q[i].l >> q[i].r; 		q[i].id = i; 	} 	sort(q + 1, q + m + 1); 	int l = 1, r = 0; 	for (int i = 1; i <= m; i++) { 		while (l < q[i].l) del(l++); 		while (r > q[i].r) del(r--); 		while (l > q[i].l) add(--l); 		while (r < q[i].r) add(++r); 		ans[q[i].id] = res; 	} 	for (int i = 1; i <= m; i++) { 		cout << ans[i] << "n"; 	} }  signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0), cout.tie(0); //	cin >> _test_; 	init(); 	while (_test_--) { 		clear(); 		solve(); 	} 	return 0; } 

不过此题块长就是 (1) 都能在 (700) 毫秒以内过，数据太水。

例题 2：小 Z 的袜子

也是非常板子的一道，维护一下 (c) 数组，并将上一题中的答案分别记分子分母即可。

请注意分子为 (0) 的情况。

#include <bits/stdc++.h> // #define int long long #define pii pair<int, int> #define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout) #define ALL(x) x.begin(), x.end() using namespace std;  int _test_ = 1;  const int N = 500008;  int n, m, k, block_size, len; pii res; int cnt[N], a[N]; pii ans[N]; struct node { 	int l, r, id; } q[N];  bool operator<(node x, node y) { 	int xl = (x.l - 1) / block_size + 1, xr = (x.r - 1) / block_size + 1; 	int yl = (y.l - 1) / block_size + 1, yr = (y.r - 1) / block_size + 1; 	return (xl != yl) ? (xl < yl) : (x.r < y.r); }  void add(int x) { 	res.first += cnt[a[x]]; 	res.second += len; 	len++; 	cnt[a[x]]++; }  void del(int x) { 	len--; 	cnt[a[x]]--; 	res.first -= cnt[a[x]]; 	res.second -= len; }  void init() {}  void clear() {}  void solve() { 	cin >> n >> m; 	for (int i = 1; i <= n; i++) { 		cin >> a[i]; 	} 	block_size = n / sqrt(m); 	for (int i = 1; i <= m; i++) { 		cin >> q[i].l >> q[i].r; 		q[i].id = i; 	} 	sort(q + 1, q + m + 1); 	int l = 1, r = 0; 	for (int i = 1; i <= m; i++) { 		if (q[i].l == q[i].r) ans[q[i].id] = {0, 1}; 		while (l < q[i].l) del(l++); 		while (r > q[i].r) del(r--); 		while (l > q[i].l) add(--l); 		while (r < q[i].r) add(++r); 		if (res.first == 0) { 			ans[q[i].id] = {0, 1}; 			continue; 		} 		int g = __gcd(res.first, res.second); 		ans[q[i].id] = {res.first / g, res.second / g}; 	} 	for (int i = 1; i <= m; i++) { 		cout << ans[i].first << "/" << ans[i].second << "n"; 	} }  signed main() { 	ios::sync_with_stdio(0); 	cin.tie(0), cout.tie(0); //	cin >> _test_; 	init(); 	while (_test_--) { 		clear(); 		solve(); 	} 	return 0; } 

事实证明，还是 (B = frac{n}{sqrt{m}}) 跑得最快。

带修莫队

由于不能带修改实在是太别扭了，所以出现了带修莫队

带修莫队的思想跟所有可持久化数据结构是差不多的。

link.

由于加进了修改，我们无法再像正常莫队一样转移了。

可以考虑在迭代时增加一维时间戳。

每次就按顺序一个一个增加或减少修改即可。

同时就要以右端点所在块编号为第二关键字、时间为第三关键字排序。

时间复杂度与最优块长

设块长为 (B)、序列长度为 (n)、询问次数为 (q)、修改次数为 (c)。

• 左右端点移动上文分析过，是 (qB + frac{n^2}{B}) 的。
• 时间指针，对于每一个块，我们至多移动 (c) 次，即 (frac{n}{B} times frac{n}{B} times c = frac{cn^2}{B^2})。

总时间复杂度为 (mathcal{O}(qB + frac{n^2}{B} + frac{cn^2}{B^2}))。

最优块长大概是……

[frac{n^2}{3^{1/3}(9m^3n^2+sqrt{3}sqrt{27m^6n^4-m^3n^6})^{1/3}}+frac{(9m^3n^2+sqrt{3}sqrt{27m^6n^4-m^3n^6})^{1/3}}{3^{2/3}m} ]

所以还是取一个更好看一点的。

譬如 (B = sqrt[3]{n^2})。

所以此时时间复杂度是约 (mathcal{O}(sqrt[3]{n^5}))。

---

总结一下，带修莫队需要满足以下条件：

• 在知道 (left [ l, r right ]) 的答案的情况下，可以 (mathcal{O}(1)) 求出 (left [ l, r + 1 right ])、 (left [ l, r - 1 right ])、 (left [ l + 1, r right ])、 (left [ l - 1, r right ]) 的答案。
• 允许离线。

优势：可以允许修改。

劣势：比思维方法慢且只能离线。、

时间复杂度：(mathcal{O}(nlog n + sqrt[3]{n^5}))​。

空间复杂度： (mathcal{O}(n))。

例题1：数颜色 / 维护队列

按上文中写的模拟即可。

#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout) #define ALL(x) x.begin(), x.end() using namespace std;  int _test_ = 1;  const int N = 2e6 + 5;   int n, m, block_size, cnt_c, cnt_q, a[N], bel[N], cnt[N], ans[N], res; struct query { 	int l, r, t, id; } c[N], q[N]; bool operator<(query x, query y) { 	return (bel[x.l] != bel[y.l]) ? (x.l < y.l) : ((bel[x.r] != bel[y.r]) ? (x.r < y.r) : (x.t < y.t)); } void build() { 	block_size = pow(n, 0.666); 	for (int i = 1; i <= n; i++) { 		bel[i] = (i - 1) / block_size + 1; 	} } void add(int x) { 	res += (cnt[x] == 0); 	cnt[x]++; } void del(int x) { 	cnt[x]--; 	res -= (cnt[x] == 0); } void upt(int x, int y) { 	if (q[y].l <= c[x].l && c[x].l <= q[y].r) { 		del(a[c[x].l]); 		add(c[x].r); 	} 	swap(a[c[x].l], c[x].r); }  void init() {}  void clear() {}  void solve() { 	cin >> n >> m; 	for (int i = 1; i <= n; i++) { 		cin >> a[i]; 	} 	build(); 	for (int i = 1; i <= m; i++) { 		char op; 		int l, r; 		cin >> op >> l >> r; 		if (op == 'Q') q[++cnt_q] = {l, r, cnt_c, cnt_q}; 		else c[++cnt_c] = {l, r, 0, 0}; 	} 	sort(q + 1, q + cnt_q + 1); 	int l = 1, r = 0, t = 0; 	for (int i = 1; i <= cnt_q; i++) { 		while (l > q[i].l) add(a[--l]); 		while (r < q[i].r) add(a[++r]); 		while (l < q[i].l) del(a[l++]); 		while (r > q[i].r) del(a[r--]); 		while (t < q[i].t) upt(++t, i); 		while (t > q[i].t) upt(t--, i);  		ans[q[i].id] = res; 	} 	for (int i = 1; i <= cnt_q; i++) cout << ans[i] << "n"; }  signed main() {   ios::sync_with_stdio(0);   cin.tie(0), cout.tie(0);   // cin >> _test_;   init();   while (_test_--) {     clear();     solve(); 	}   return 0; }