简介

用于解决一类离线区间询问问题。将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队算法

概述

对于序列上的区间询问问题，如果从 \([l, r]\) 答案能够 \(O(1)\) 扩展到 \([l - 1, r],[l + 1, r],[l, r + 1],[l, r - 1]\)（即与 \([l, r]\) 相邻的区间）的答案，那么可以在 \(O(n \sqrt n)\) 的复杂度内求出所有询问的答案。

例题

HH的项链

做法概述

先将每次询问的区间离线下来，然后进行排序，再顺序处理每个询问，暴力从上一个区间转移到下一个区间。

排序方法：对于这些区间（\([l, r]\)），右端点（\(l\)）单调，左端点（\(r\)）用分块的思想进行处理。左端点（\(r\)）按分块编号排序，若编号不同，则从小到大排序；若编号相同，则按右端点（\(l\)）下标从小到大排序（双关键字排序）。

实现

struct Query {
	int id, l, r;
} q[S];

int cnt[S];

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int i = get(a.l), j = get(b.l);
	if (i != j) return i < j;
	return a.r < b.r;
}

void add(int x, int &res) {
	cnt[x]++;
	if (cnt[x] == 1) res++;
}

void del(int x, int &res) {
	cnt[x]--;
	if (cnt[x] == 0) res--;
}

void solve() {
	for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++ ) {// j 为左端点，i 为右端点
		int id = q[k].id, l = q[k].l, r = q[k].r;
		while (i < r) add(w[ ++ i], res);
		while (i > r) del(w[i -- ], res);
		while (j < l) del(w[j ++ ], res);
		while (j > l) add(w[ -- j], res);
		ans[id] = res;
	}
}

int main() {
	n = read();
	for (int i = 1; i <= n; i ++ ) w[i] = read();
	m = read();
	len = sqrt((double)n);
	for (int i = 0; i < m; i ++ ) {
		int l = read(), r = read();
		q[i] = {i, l, r};
	}
	sort(q, q + m, cmp);
	solve();
	for (int i = 0; i < m; i ++ ) write(ans[i]), puts("");
	return 0;
}

一些优化：

1. 可以适当将块长增长。

   设块长为 \(a\)，则共有 \(\frac n a\) 块。

   右端点（\(r\)）：\(n \times \frac{n}{a} = \frac{n^2}{a}\)

   左端点（\(l\)）：\(m \times a = am\)

   当 \(\frac{n ^ 2}{a} = am\) 时，速度最快。

   解得 \(a = \sqrt{\frac{n ^ 2}{m}}\)。

   所以上面的代码中第 42 行就可以改成：

   len = sqrt((double)n * n / m);

2. 进行奇偶排序

   奇数块递增排序，偶数块递减排序（反之亦可）（不太好证明，在此不作解释）。

   struct node {
   	int id, l, r;
   	
   	bool operator < (const node &x) const {
   		if (l / len != x.l / len) return l < x.l;
   		if ((l / len) & 1) return r < x.r;
   		return r > x.r;
   	}
   };
   

   细节,如果使用 sort 比较两个函数,不能出现 a < b 和 a > b 同时为真的情况,否则会运行错误

复杂度分析

\(O(n \sqrt m)\)

（不想写了，暂时先不展开写）

带修改莫队

特点

强行让普通莫队待修改，像 DP 一样，强行加上一维时间维，表示这次操作的时间。

时间维表示经历的修改次数。

即把询问 \([l, r]\) 变成 \([l, r, time]\)。

那么坐标也可以在时间维上移动，即 \([l, r, time]\) 多了一维可以移动的方向，可以变成：

• \([l - 1, r, time]\)

• \([l + 1, r, time]\)

• \([l, r - 1, time]\)

• \([l, r + 1, time]\)

• \([l, r, time - 1]\)

• \([l, r, time + 1]\)

这样转移也是 \(O(1)\) 的，只是排序又多了一个关键字。

可以用和普通莫队类似的方法排序转移，做到 \(O(n^\frac 5 3)\)。

这一次的排序方式是以 \(n^\frac 2 3\) 为一块，分成了 \(n^\frac 1 3\) 块。

第一关键字是左端点所在块，第二关键字是右端点所在块（不同于普通莫队），第三关键字是时间。

最优块长及时间复杂度分析：

（要求导啊！！！不会啊！！！）那就直接上结论吧……

当块长取 \(\frac{n^\frac 2 3 t ^ \frac 1 3}{m ^ \frac 1 3}\) 时有最优时间复杂度 \(O(n^\frac 2 3 m ^\frac 2 3 t ^ \frac 1 3)\)。

常说的 \(O(n^\frac 5 3)\) 便是把 \(n, m, t\) 当作同数量级的时间复杂度。

例题

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

题目大意：给定一个序列，\(M\) 个操作。

有两种操作：

1. 修改序列上某一位的数字

2. 询问区间 \([l, r]\) 中数字的种类数（多个相同数字只算一个）

可以发现，如果没有操作 1（修改）的话，用普通莫队就可以解决，但是题目带有单点修改，所以用带修改的莫队。

过程

首先是普通莫队（具体过程略），接下来考虑修改（单点修改）：

• 把某一位的数字修改掉。加入我们是从一个经理修改次数为 &i& 的询问转移到修改次数为 \(j\) 的询问上。若 \(i < j\)，我们需要把第 \(i + 1\) 个到第 \(j\) 个修改强行加上；若 \(i > j\)，则需要把第 \(i\) 个到第 \(j + 1\) 个修改强行还原。

• 例如，我们从修改次数为 \(3\) 的询问转移到修改次数为 \(5\) 的询问上，那么就需要加上第 \(4, 5\) 次修改，反之，就要将第 \(4, 5\) 次修改还原。

修改过程：

1. 若在区间内，则删除原有的数，再加上改变后的的数；

2. 若不在区间内，\(cnt\) 不变，直接修改该项为改变后的数（看代码）

3. trick：修改时，善于运用 swap 函数，交换即可，这样在还原的时候便于再交换回来（看代码）。

实现

#include <bits/stdc++.h>

using namespace std;

const int N = 133335, S = 1000010;

int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];

struct Query {
	int id, l, r, t;
} q[N];

struct Modify {
	int p, c;
} c[N];

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int al = get(a.l), ar = get(a.r);
	int bl = get(b.l), br = get(b.r);
	if (al != bl) return al < bl;
	if (ar != br) return ar < br;
	return a.t < b.t;
}

void add(int x, int &res) {
	res += !cnt[x]++;
}

void del(int x, int &res) {
	res -= !--cnt[x];
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", w + i);
	for (int i = 0; i < m; i ++ ) {
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		if (*op == 'Q') mq ++, q[mq] = (Query) {mq, a, b, mc};
		else c[ ++ mc] = (Modify) {a, b};
	}
	len = pow(n, 2.0 / 3.0);//虽然但是，不知道为啥，
	//块长设置为 cbrt((double)n * mc) + 1 就是不行
	//块长设置成这样才能过
	//这个是当 n 和 t 是同一数量级的时候的块长
	sort(q + 1, q + mq + 1, cmp);
	for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++ ) {
		int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
		while (i < r) add(w[ ++ i], res);
		while (i > r) del(w[i -- ], res);
		while (j < l) del(w[j ++ ], res);
		while (j > l) add(w[ -- j], res);
		while (t < tm) {
			t ++ ;
			if (c[t].p >= j && c[t].p <= i) {
				del(w[c[t].p], res);
				add(c[t].c, res);
			}
			swap(w[c[t].p], c[t].c);
		}
		while (t > tm) {
			if (c[t].p >= j && c[t].p <= i) {
				del(w[c[t].p], res);
				add(c[t].c, res);
			}
			swap(w[c[t].p], c[t].c);
			t -- ;
		}
		ans[id] = res;
	}
	for (int i = 1; i <= mq; i ++ ) printf("%d\n", ans[i]);
	return 0;
}

回滚莫队

引入

有些题目在区间转移时，可能会出现增加或删除无法实现，那么这个时候就要使用回滚莫队，时间复杂度是 \(O(n \sqrt m)\)。

核心思想：既然只能实现一个操作，那就只使用一个操作，剩下的用回滚解决。

下面介绍插入简单，删除不易的回滚莫队：

首先，和普通莫队一样，是双关键字排序：

1. \(l\) 所在块的编号；

2. \(r\) 右端点下标。

处理询问时分两种：

1. 块内。暴力求即可，这样，剩下的必然在块间（跨块）。

2. \(j\) 是左端点，\(i\) 是右端点，假设询问区间包含了块 \(1\) 的后半截和块 \(2\) 的前半截，那么处理时分成两个部分——在块 \(1\) 内的部分 和 不在块 \(1\) 内的部分。先说第二个部分，此时 \(cnt\) 和 \(res/sum/ans\) 维护的不是整个区间，而是块 \(2\) 中询问的部分。\(j\) 应从块 \(2\) 的第一个位置开始，\(i\) 应在块 \(1\) 与块 \(2\) 的分界线上（此时区间为空）。至于第一个部分，长度一定小于等于 \(\sqrt n\)，所以可以暴力加，之后再暴力删（\(cnt\) 更新，不用维护 \(res\)，\(res\) 只存初始的（备份）（具体看代码））。

回滚指的就是暴力加，再回滚删除。

例题

歴史の研究

给定一个长度为 \(n\) 的数组 \(A\) 和 \(m\) 个询问（\(1 \leqslant n, m \leqslant 10^5\)），每次询问一个区间 \([L, R]\) 内重要度最大的数字，要求输出其重要度。一个数字 \(i\) 的重要度定义为 \(i \) 乘上 \(i\) 在区间内出现的次数。

实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m, len;
int w[N], cnt[N];
long long ans[N];

struct Query {
	int id, l, r;
} q[N];

vector <int> nums;

int get(int x) {
	return x / len;
}

bool cmp(const Query &a, const Query &b) {
	int i = get(a.l), j = get(b.l);
	if (i != j) return i < j;
	return a.r < b.r;
}

void add(int x, long long &res) {
	cnt[x]++;
	res = max(res, (long long)cnt[x] * nums[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	len = sqrt(n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	for (int i = 1; i <= n; i ++ )
		w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
		//离散化
	for (int i = 0; i < m; i ++ ) {
		int l, r;
		scanf("%d%d", &l, &r);
		q[i] = (Query) {i, l, r};
	}
	sort(q, q + m, cmp);
	
	for (int x = 0; x < m;) {
		int y = x;
		while (get(q[y].l) == get(q[x].l) && y < m) y ++ ;
		int right = get(q[x].l) * len + len - 1;
		while (x < y && q[x].r <= right) {
			long long res = 0;
			int id = q[x].id, l = q[x].l, r = q[x].r;
			for (int k = l; k <= r; k ++ ) add(w[k], res);
			ans[id] = res;
			for (int k = l; k <= r; k ++ ) cnt[w[k]] -- ;
			x ++ ;
		}
		long long res = 0;
		int i = right, j = right + 1;
		while (x < y) {
			int id = q[x].id, l = q[x].l, r = q[x].r;
			while (i < r) add(w[ ++ i], res);
			long long bres = res;
			while (j > l) add(w[ -- j], res);
			ans[id] = res;
			while (j < right + 1) cnt[w[j ++ ]] -- ;
			res = bres;
			x ++ ;
		}
		memset(cnt, 0, sizeof cnt);
	}
	for (int i = 0; i < m ; i ++ ) printf("%lld\n", ans[i]);
	return 0;
}

复杂度证明

假设块长为 \(a\)：

• 对于左右端点在同一个块内的询问，可以在 \(O(b)\) 时间内计算；

• 对于其他询问，考虑左端点在相同块内的询问，他们的右端点单调递增，移动右端点的时间复杂度是 \(O(n)\)，而左端点单次询问的移动不超过 \(a\)，因为有 \(\frac n a\) 个块，所以总复杂度是 \(O(am + \frac {n^2} {a})\)，取 \(a = \frac n {\sqrt m}\) 最优，时间复杂度为 \(O(n \sqrt m)\)。

参考资料：AcWing、Oi Wiki、《算法训练营》

本栏目推荐文章
• 浅谈莫队2
• 浅谈莫队
• 莫队学习笔记
• 莫队
• 详细揭秘：子树补回滚莫队线性对数解法
• 莫队
• 树套树板子，但是带修莫队+值域分块
• 莫队的时间复杂度胡扯
• 算法笔记（4）莫队算法入门
• 【学习笔记】莫队