普通莫队

如果可以较快地使询问区间从 $[l, r]$ 转移到 $[l, r + 1], [l, r - 1], [l + 1, r], [l - 1, r]$ （加入 / 删除元素），那么就能用普通莫队解决本题。

将区间分成 $\sqrt n$ 个块，询问按照左端点所在的块编号（第一关键字）和右端点（第二关键字）排序即可。

排序后，两个端点会移动 $n \sqrt n$ 次。

证明

因为左端点的移动和右端点的移动互不影响，我们先考虑左端点的移动。

设第 $i$ 块里的左端点最大值为 $maxl_i$ 。

因为对左端点所在的块编号排过序，所以 $maxl_1 \le maxl_2 \le maxl_3 \le \cdots \le maxl_{\lceil\sqrt n\rceil}$ 。

在最坏情况下，第 $i$ 块的左端点会在 $[maxl_{i - 1}, maxl_{i}]$ 之间左右移动，移动 $\sqrt n$ 次，所以移动了 $\sqrt n \times (maxl_i - maxl_{i - 1})$ 次。

每一块的移动次数之和为：

\begin{aligned} & \sqrt n \times (maxl_1 - 1) + \sqrt n \times (maxl_2 - maxl_1) + \cdots + \sqrt n \times (maxl_n - maxl_{n - 1}) \\ = \ & \sqrt n \times (maxl_1 - 1 + maxl_2 - maxl_1 + maxl_n - maxl_{n - 1}) \\ = \ & \sqrt n \times (maxl_n - 1) \\ = \ & n \sqrt n\end{aligned}

右端点在每块里都已经排好序，每一个块移动的次数为 $n$ ， $\sqrt n$ 块移动的次数就是 $n \sqrt n$ 。

左右端点的移动次数都是 $n \sqrt n$ ，证毕。

如果可以 $O(1)$ 加入 / 删除一个元素，普通莫队的时间复杂度就是 $O(n \sqrt n)$ 。

小 Z 的袜子代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
ll gcd(ll a, ll b){
	if (!b) return a;
	return gcd(b, a % b);
}
struct que{
	int l, r, id;
}q[50001];
bool cmpl(que a, que b){return a.l < b.l;}
bool cmpr(que a, que b){return a.r < b.r;}

using namespace std;

int n, m, a[50001];
int len, cnt, L[301], R[301], l, r;
ll ans[50001], b[50001], g, t[50001], sum;
inline void add(int x){sum -= t[x] * (t[x] - 1), t[x] ++, sum += t[x] * (t[x] - 1);}
inline void pop(int x){sum -= t[x] * (t[x] - 1), t[x] --, sum += t[x] * (t[x] - 1);}
inline void getans(int i){
	int id = q[i].id;
	if (q[i].l == q[i].r){
		ans[id] = 0, b[id] = 1;
		return;
	}
	ans[id] = sum;
	b[id] = 1ll * (q[i].r - q[i].l) * (q[i].r - q[i].l + 1);
	g = gcd(ans[id], b[id]);
	ans[id] /= g, b[id] /= g;
	if (b[id] == 0) ans[id] = 1;
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	for (int i = 1;i <= m;i ++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	sort(q + 1, q + m + 1, cmpl);
	len = sqrt(m);
	for (int i = 1;i <= m / len;i ++) cnt ++, L[cnt] = (i - 1) * len + 1, R[cnt] = i * len;
	if (R[cnt] < m) cnt ++, L[cnt] = R[cnt - 1] + 1, R[cnt] = m;
	for (int i = 1;i <= cnt;i ++) sort(q + L[i], q + R[i] + 1, cmpr);
	l = q[1].l, r = q[1].r;
	for (int i = l;i <= r;i ++) add(a[i]);
	getans(1);
	for (int i = 2;i <= m;i ++){
		while (q[i].l < l) add(a[-- l]);
		while (l < q[i].l) pop(a[l ++]);
		while (r < q[i].r) add(a[++ r]);
		while (q[i].r < r) pop(a[r --]);
		getans(i);
	}
	for (int i = 1;i <= m;i ++) printf("%d/%d\n", ans[i], b[i]);
}

带修莫队

普通的莫队不支持带修，我们可以给每一个询问加上一个 $t$ ，表示经历了前 $t$ 次修改。

如果可以较快地使询问区间从 $[l, r, t]$ 转移到 $[l, r + 1, t], [l, r - 1, t], [l + 1, r, t], [l - 1, r, t], [l, r, t + 1], [l, r, t - 1]$ （应用一次修改以及撤销一次修改），那么就能用带修莫队解决本题。

带修莫队与普通莫队类似，将区间分成 $n^{\frac{1}{3}}$ 块，询问按照左端点所在的块编号（第一关键字）,右端点所在的块编号（第二关键字）和时间（第三关键字）排序。

排序后，两个端点与时间的移动次数为 $n^{\frac{5}{3}}$ 。

证明

左端点块编号有 $n^{\frac{1}{3}}$ 种，右端点的块编号也有 $n^{\frac{1}{3}}$ 种，对于每一种块编号，时间 $t$ 都是单调的，移动 $n$ 次，于是一共移动 $n^{\frac{1}{3}} \times n^{\frac{1}{3}} \times n = n^{\frac{5}{3}}$ 次。

[国家集训队] 数颜色 / 维护队列代码：

#include <cstring>
#include <cstdio>
#include <cmath>
struct upd{
	int p, x;
}s[200001];
struct que{
	int l, r, t, id;
}q[200001];

using namespace std;

int n, T, m, _, a[200001], len;
int l, r, t, sum, c[1000001], ans[200001];
char op;
bool cmp(que a, que b){return a.l / len == b.l / len ? (a.r / len == b.r / len ? a.t < b.t : a.r / len < b.r / len) : a.l / len < b.l / len;}
inline void add(int x){sum += c[x] == 0, c[x] ++;}
inline void rem(int x){sum -= c[x] == 1, c[x] --;}
inline void upd(int i, int x){
	if (q[i].l <= s[x].p && s[x].p <= q[i].r) rem(a[s[x].p]), add(s[x].x);
	swap(a[s[x].p], s[x].x); // 由于每一次操作或撤销操作后的行动肯定是相反的，所以只需要写一个 upd 函数，然后 swap 一下即可
}
int main(){
	scanf("%d%d", &n, &T);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	for (int i = 1;i <= T;i ++){
		scanf(" %c", &op);
		if (op == 'Q') m ++, scanf("%d%d", &q[m].l, &q[m].r), q[m].t = _, q[m].id = m;
		else _ ++, scanf("%d%d", &s[_].p, &s[_].x);
	}
	len = pow(n, 2.0 / 3);
	sort(q + 1, q + m + 1, cmp);
	for (int i = 1;i <= m;i ++){
		while (q[i].l < l) add(a[-- l]);
		while (l < q[i].l) rem(a[l ++]);
		while (r < q[i].r) add(a[++ r]);
		while (q[i].r < r) rem(a[r --]);
		while (t < q[i].t) upd(i, ++ t);
		while (q[i].t < t) upd(i, t --);
		ans[q[i].id] = sum;
	}
	for (int i = 1;i <= m;i ++) printf("%d\n", ans[i]);
}

回滚莫队

回滚莫队，就是普通莫队的拓展。

当一个区间加入 / 删除元素这两种操作中只能快速实现一个，而无法快速实现另一个的时候，就可以使用回滚莫队。

我们使用只实现加入操作而不实现删除操作的回滚莫队举例来讲解回滚莫队。

首先，将原序列分成块长为 $b$ 的 $\left\lceil\dfrac{n}{b}\right\rceil$ 块，对每个询问按照左端点所处的块（第一关键字）和右端点所处的块（第二关键字）排序。

然后，依次回答每一个询问。

如果当前询问左端点所在的块 $B$ 与莫队区间左端点 $l$ 所在的块不同，就将 $l$ 移到 $B$ 的右端点 $+ 1$ ，莫队区间右端点 $r$ 移到 $B$ 的右端点，使莫队区间为空。

如果当前询问左端点和右端点在同一块内，直接回答即可。

否则先拓展 $r$ （因为排序后询问左端点位于同一块内，右端点单调上升），再“临时”拓展 $l$ 。

回答询问后，将拓展 $l$ 加入元素产生的更改撤销，使 $l$ 重新位于 $B$ 的右端点 $+1$ 处。

复杂度分析

对于在同一块内的询问，可以在 $O(b)$ 的时间复杂度内回答。

对于同一块内的左端点，右端点单调上升，滚动右端点的时间为 $O(n)$ 。左端点只会在同一个块内滚动，时间复杂度为 $O(b)$ 。

总时间复杂度为 $O(mb + \frac{n^2}{b})$ ， $b$ 取 $\dfrac{n}{\sqrt m}$ 最优，时间复杂度为 $O(n \sqrt m)$ 。

歴史の研究代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
struct que{
	int l, r, id;
}q[200001];

using namespace std;

int n, m, a[200001], b[200001], _, len;
int l, r, tl, lb, c[200001], c2[200001];
ll sum, tmp, ans[200001];
bool cmp(que a, que b){return a.l / len == b.l / len ? a.r < b.r : a.l / len < b.l / len;}
inline void add(int x, ll& sum){c[x] ++, sum = max(sum, 1ll * c[x] * b[x]);}
inline void rem(int x){c[x] --;}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[++ _]  = a[i];
	sort(b + 1, b + _ + 1);
	_ = unique(b + 1, b + _ + 1) - b - 1;
	for (int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1, b + _ + 1, a[i]) - b;
	for (int i = 1;i <= m;i ++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	len = n / sqrt(m);
	sort(q + 1, q + m + 1, cmp);
	for (int i = 1;i <= m;i ++){
		if (q[i].l / len == q[i].r / len){
			for (int j = q[i].l;j <= q[i].r;j ++) c2[a[j]] ++;
			for (int j = q[i].l;j <= q[i].r;j ++) ans[q[i].id] = max(ans[q[i].id], 1ll * c2[a[j]] * b[a[j]]);
			for (int j = q[i].l;j <= q[i].r;j ++) c2[a[j]] --;
			continue;
		} // 暴力回答
		if (q[i].l / len + 1 != lb){
			while (l < (q[i].l / len + 1) * len + 1) rem(a[l ++]);
			while ((q[i].l / len + 1) * len < r) rem(a[r --]);
			sum = 0;
			lb = q[i].l / len + 1;
		} // 清空莫队区间
		while (r < q[i].r) add(a[++ r], sum); // 右端点往右
		tl = l, tmp = sum;
		while (q[i].l < tl) add(a[-- tl], tmp); // 临时将左端点移动
		ans[q[i].id] = tmp;
		while (tl < l) rem(a[tl ++]); // 撤销更改
	}
	for (int i = 1;i <= m;i ++) printf("%lld\n", ans[i]);
}

例题

菜王的 blog

莫队学习笔记

普通莫队

证明

带修莫队

证明

回滚莫队

复杂度分析

例题

下一篇：整体二分学习笔记