Creator's World

Hello World!

首页 归档 标签 关于

莫队

2021-05-23 22 min read

1. 普通莫队

1.1. 简介

莫队是一种解决离线区间询问问题的算法，运用分块的思想。设区间长度 nn 和 询问次数 mm 同阶，时间复杂度为 O(nn)O(n\sqrt{n})。

莫队的核心思想就是将区间查询离线存下来（形如 [l,r][l,r]），通过对所有询问进行排序，然后通过暴力移动区间的左右端点并快速更新答案得到所有询问的结果。

1.2. 例题

P2709 小B的询问

1.2.1. 题意

有一个长度为 nn 的序列 aa 满足 ai∈[1,k]a_i\in[1,k]，有 mm 次询问，每次询问一个区间 [l,r][l,r] 中 ∑i=1kci2\sum_{i=1}^{k}c_i^2 的值，cic_i 表示 ii 在 [l,r][l,r] 中的出现次数。

1.2.2. 思路

首先最暴力的想法就是对于每一个区间 [l,r][l,r] 都扫一遍，对于每个 aia_i，都让 cai←cai+1c_{a_i} \leftarrow c_{a_i} + 1，然后直接计算。时间复杂度为 O(m(n+k))O(m(n+k))，显然过不了。

但我们发现对于每次 cai←cai+1c_{a_i} \leftarrow c_{a_i} + 1 我们可以直接求出对答案的贡献是 2cai+12c_{a_i}+1，那么这样就与 kk 无关，时间复杂度为 O(nm)O(nm)。

再思考发现有一些区间并不需要每次重新计算，可以依托于之前算过的区间直接得出答案。比如 [1,5][1, 5] 和 [2,6][2,6] 差距并不大，计算出前一个区间的之后，后面的区间只需要减去 11 的贡献再加上 66 的贡献即可。cai←cai−1c_{a_i} \leftarrow c_{a_i} - 1 使答案减少 2cai−12c_{a_i} - 1，因此我们可以通过上一个询问更新下一个区间的答案。

但这样还是有可能被卡到 O(nm)O(nm) 的，接下来是莫队的关键，也就是保证时间复杂度为 O(nn)O(n\sqrt{n}) 的秘诀。首先我们将整个区间分成几个长度为 blockblock 的块，这就是数列分块。然后对于所有所有区间 [l,r][l,r]，以 ll 所在的块编号为第一关键字，rr 为第二关键字从小到大排序。

接下来证明时间复杂度为何保证为 O(nn)O(n\sqrt{n})，首先左端点因为把同一块同放在一起，所有一次询问时间复杂度为 O(block)O(block)，mm 次询问就是 O(mblock)O(mblock)。而右端点由于单调递增，最多移动 nn 次，由于有 nblock\frac{n}{block}，所以整体时间复杂度为 O(n2block)O(\frac{n^2}{block})。所以总复杂度为 O(mblock+n2block)O(mblock+\frac{n^2}{block})，显然 mblcok=n2blockmblcok = \frac{n^2}{block} 最优，所以 block=n2mblock = \sqrt{\frac{n^2}{m}}，假定 n,mn,m 同届，设 n=mn=m，block=nblock = \sqrt{n} 时时间复杂度为 O(nn)O(n\sqrt{n}) 最优。

1.2.3. 代码

#include<bits/stdc++.h>
#define ln puts("")
#define sp printf(" ")
using namespace std;
typedef long long ll;

inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

void write(ll x) {
	if(x < 0)
		putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 5e4 + 7;
int n, m, k, a[N], block, l = 1, r, ans[N], nowans, cnt[N];
struct node {
	int l, r, id, belong;
	bool operator< (const node &x) const {
		if(belong == x.belong)
			return r < x.r;
		return belong < x.belong;
	}
}ask[N];

int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	n = read(), m = read(), k = read();
	block = sqrt(n);
	for(int i = 1; i <= n; i++)
		a[i] = read();
	for(int i = 1; i <= m; i++)
		ask[i].l = read(), ask[i].r = read(), ask[i].id = i, ask[i].belong = (ask[i].l - 1) / block + 1;
	sort(ask + 1, ask + 1 + m);
	for(int i = 1; i <= m; i++) {
		while(ask[i].l < l)
			l--, cnt[a[l]]++, nowans += 2 * cnt[a[l]] - 1;
		while(ask[i].r > r)
			r++, cnt[a[r]]++, nowans += 2 * cnt[a[r]] - 1;
		while(ask[i].l > l)
			cnt[a[l]]--, nowans -= 2 * cnt[a[l]] + 1, l++;
		while(ask[i].r < r)
			cnt[a[r]]--, nowans -= 2 * cnt[a[r]] + 1, r--;
		ans[ask[i].id] = nowans;
	}
	for(int i = 1; i <= m; i++)
		write(ans[i]), ln;
	return 0;
}

1.3. 流程

  1. 将序列进行分块操作；

  2. 对于区间询问操作离线存下来，再按照某种规律进行排序；

  3. 对于每一个区间，通过前面得到的答案再左右移动得到答案。

1.4. 其他题目

P1494 [国家集训队]小Z的袜子

题意：

有一个长度为 nn 的区间 aa，给你 mm 次询问 [l,r][l,r]，对于每次询问求出从区间随机选两个数相同的概率。

思路：

一看下去没有想法，但考虑如何计算概率。若有 kk 种不同的颜色，每种颜色 ii 有 cnticnt_i 个，则答案为 ∑i=1kcnti×(cnti−1)(r−l+1)×(r−l)=∑i=1kcnti2−(r−l+1)(r−l+1)×(r−l)\frac{\sum_{i=1}^kcnt_i\times (cnt_i-1)}{(r-l+1)\times (r-l)} = \frac{\sum_{i=1}^kcnt_i^2-(r-l+1)}{(r-l+1)\times (r-l)}，而问题又变成了快速求出区间每个数出现次数的平方，也就是上面的题目了。

SP3267 DQUERY - D-query

题意：

询问区间 [l,r][l,r] 有多少不同的数。

思路：

类似的莫队，通过判断计数数组 cntaicnt_{a_i} 是否为 1/01/0 更新答案。

P4867 Gty的二逼妹子序列

题意：

询问区间 [l,r][l,r] 有多少种数满足其值在 [a,b][a,b] 间。

思路：

看到区间查询显然用莫队可以很简单地做，但是这个查询却有些不同。不过 [a,b]≤n[a,b] \leq n 这个性质很有用，我们可以用值域分块来查询。

2. 带修莫队

2.1. 简介

带修莫队相对于普通莫队来说，可以处理单点修改的操作。相比于普通的莫队我们再加上一个维度：该维度表示当前询问已经进行了几次修改，然后对这一维也进行排序。

2.2. 例题

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

2.2.1. 题意

给出一个长度为 nn 的序列 aa，有 mm 次修改或查询的操作，每次查询给出 [l,r][l,r]，求 [l,r][l,r] 出现多少不同的数。

2.2.2. 思路

没有修改的做法我们已经会了，但加上修改的操作又该如何处理呢？

和普通的莫队几乎一样，只不过给每个询问操作都加上一个时间戳 tt，表示在该次询问之前已经修改过了 tt 次，因为修改操作顺序是固定的，因此我们很容易可以每次询问前都修改过哪些。

考虑如何进行处理。先和普通莫队一样处理完 ll 和 rr，然后再对一个对 tt 的处理。我们记录下每次修改的位置和值，然后若新加入了一个修改，我们判断它是否在询问区间 [l,r][l,r] 之间，若是的话则更新答案。这里有个很重要的细节，每次更新完一个修改操作的时候，我们都要将原先值和修改值交换一下，因为一开始我们更新这个修改是因为要加上这个操作，是将原先值变成修改值；而再更新这个操作是因为要减去这个操作，是将修改值变成原先值，如此反复，因此每次要交换。

在排序的时候，以左端点所在块的编号为第一关键字，右端点所在块的编号为第二关键字，在此之前修改过的次数为第三关键字，从小到大排序。

块长取 n23n^{\frac{2}{3}} 时最优。

2.2.3 代码

#include<bits/stdc++.h>
#define ln puts("")
#define sp printf(" ")
using namespace std;
typedef long long ll;

inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

void write(ll x) {
	if(x < 0)
		putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 1e6 + 7;
int n, m, block, a[N], ans[N], l = 1, r, cnta, cntm, cntt, sum, cnt[N];
struct node {
	int l, r, id, t;
	bool operator< (const node &x) {
		return l / block == x.l / block ? r / block == x.r / block ? t < x.t : r < x.r : l < x.l;
	}
}ask[N], mod[N];

void add(int x) {
	cnt[x]++;
	sum += (cnt[x] == 1);
}

void del(int x) {
	cnt[x]--;
	sum -= (cnt[x] == 0);
}

void upd(int x, int t) {
	if(ask[x].l <= mod[t].l && mod[t].l <= ask[x].r)
		del(a[mod[t].l]), add(mod[t].r);
	swap(a[mod[t].l], mod[t].r);
}

int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	n = read(), m = read();
	block = pow(n, 0.666); 
	for(int i = 1; i <= n; i++)
		a[i] = read();
	for(int i = 1; i <= m; i++) {
		char ch;
		int x, y;
		cin >>ch;
		x = read(), y = read();
		if(ch == 'Q')
			ask[++cnta].l = x, ask[cnta].r = y, ask[cnta].id = cnta, ask[cnta].t = cntm;
		else
			mod[++cntm].l = x, mod[cntm].r = y;
	}	
	sort(ask + 1, ask + 1 + cnta);
	for(int i = 1; i <= cnta; i++) {
		while(ask[i].l < l)
			l--, add(a[l]);
		while(ask[i].r > r)
			r++, add(a[r]);
		while(ask[i].l > l)
			del(a[l]), l++;
		while(ask[i].r < r)
			del(a[r]), r--;
		while(ask[i].t > cntt)
			cntt++, upd(i, cntt);
		while(ask[i].t < cntt)
			upd(i, cntt), cntt--;
		ans[ask[i].id] = sum;
	}
	for(int i = 1; i <= cnta; i++)
		write(ans[i]), ln;
	return 0;
}

2.3. 其他例题

CF940F Machine Learning

本质就是普通的带修莫队，不过一开始不知道这个 mex⁡\operatorname{mex} 不知道怎么求。其实可以直接暴力计算，假设答案为 xx，那么一定存在 1,2,3,⋯ ,x−11,2,3,\cdots,x-1，其复杂度为 nnn\sqrt{n}，不会影响复杂度。

3. 树上莫队

3.1. 简介

树上莫队相比于普通莫队可以用来维护树上的信息。显然通常用数据结构维护树上信息都是通过某种方式将树变成一个序列，一般使用 dfs 序，但其无法处理 lca 的情况，因此要用到一个叫欧拉序的东西。

欧拉序其实和普通的 dfs 差别不大，只不过记录了每个节点入栈和出栈的时间。

3.2. 例题

SP10707 COT2 - Count on a tree II

3.2.1. 题意

在一棵节点数为 nn 的树上，每个点都有颜色。给出 mm 次询问，每次询问给出 [u,v][u,v]，求出树上 [u,v][u,v] 的最短路径上有多少不同颜色。

3.2.2. 思路

首先通过树链剖分求出欧拉序，也便于下面求 lca。然后对于每次查询 [u,v][u,v]，我们先保证 stu<stvst_u<st_v，然后分两种情况考虑：

  1. vv 在 uu 的子树中，即 uu 和 vv 的 lca 等于 uu。这时我们取区间 [stu,stv][st_u,st_v]，容易发现区间里出现仅一次的点才会在路径上，因此我们对每个数打标记，为 11 则删，否则的话加，每次操作完后标记取反。

  2. vv 不在 uu 的子树中，即 uu 和 vv 的 lca 不等于 uu。这时我们取区间 [edu,stv][ed_u,st_v]，然后发现没有 lca，因此要特判一下。

然后就是普通莫队。

3.2.3. 代码

#include<bits/stdc++.h>
#define ln puts("")
#define sp printf(" ")
using namespace std;
typedef long long ll;

inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

void write(ll x) {
	if(x < 0)
		putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 2e5 + 7;
int n, m, a[N], data[N], l = 1, r, sum, ans[N];
struct edge {
	int to, nxt;
}e[N];
int cnt, he[N];

void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = he[u];
	he[u] = cnt;	
}

void dic() {
	for(int i = 1; i <= n; i++)
		data[i] = a[i];
	sort(data + 1, data + 1 + n);
	int tot = unique(data + 1, data + 1 + n) - data;
	for(int i = 1; i <= n; i++)
		a[i] = lower_bound(data + 1, data + 1 + tot, a[i]) - data;
}
//deep top fa siz son num
int deep[N], top[N], fa[N], siz[N], num[N], son[N], dfs_cnt, st[N], ed[N];

void dfs1(int u, int fat) {
	deep[u] = deep[fat] + 1;
	fa[u] = fat;
	siz[u] = 1;
	st[u] = ++dfs_cnt;
	num[dfs_cnt] = u;
	for(int i = he[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fat)
			continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])
			son[u] = v;
	}	
	ed[u] = ++dfs_cnt;
	num[dfs_cnt] = u;
}

void dfs2(int u, int tp) {
	top[u] = tp;
	if(!son[u])
		return;
	dfs2(son[u], tp);
	for(int i = he[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(top[v])
			continue;
		dfs2(v, v);
	}
}

int lca(int x, int y) {
	while(top[x] != top[y]) {
		if(deep[top[x]] < deep[top[y]])
			swap(x, y);
		x = fa[top[x]];
	}	
	return deep[x] < deep[y] ? x : y;
}

int block;
struct node {
	int l, r, id, belong, lca;
	bool operator< (const node &x) const {
		if(belong == x.belong)
			return r < x.r;
		return l < x.l;
	}
}ask[N];

void get_ask() {
	for(int i = 1; i <= m; i++) {
		int x = read(), y = read();
		if(st[x] > st[y])
			swap(x, y);
		int tmp = lca(x, y);
		ask[i].id = i;
		if(tmp == x)
			ask[i].l = st[x], ask[i].r = st[y], ask[i].belong = (st[x] - 1) / block + 1;
		else
			ask[i].l = ed[x], ask[i].r = st[y], ask[i].belong = (ed[x] - 1) / block + 1, ask[i].lca = tmp; 
	}
}

bool vis[N];
int tot[N];

void add(int x) {
	tot[x]++;
	sum += tot[x] == 1;
}

void del(int x) {
	tot[x]--;
	sum -= tot[x] == 0;
}

void upd(int x) {
	vis[x] ? del(a[x]) : add(a[x]), vis[x] ^= 1;	
}

int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	n = read(), m = read();
	for(int i = 1; i <= n; i++)
		a[i] = read();
	dic();
	
//	for(int i = 1; i <= n; i++)
//		write(a[i]), sp;

	for(int i = 1; i <= n - 1; i++) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	
//	for(int i = 1; i <= dfs_cnt; i++)
//		write(num[i]), sp;

	block = sqrt(n);
	get_ask();
	sort(ask + 1, ask + 1 + m);
	for(int i = 1; i <= m; i++) {
		while(ask[i].l < l)
			l--, upd(num[l]);
		while(ask[i].r > r)
			r++, upd(num[r]);
		while(ask[i].l > l)
			upd(num[l]), l++;
		while(ask[i].r < r)
			upd(num[r]), r--;
		if(ask[i].lca)
			upd(ask[i].lca);
		ans[ask[i].id] = sum;
		if(ask[i].lca)
			upd(ask[i].lca);		
	}
	for(int i = 1; i <= m; i++)
		write(ans[i]), ln;
	return 0;
}

3.3. 其他例题

P4074 [WC2013] 糖果公园

首先理解题意，我们发现题目让我们查询的就是 [u,v][u,v] 的最短路径的 ∑i=1mvi×∑j=1cntiwj\sum_{i=1}^m v_i\times \sum_{j=1}^{cnt_i}w_j，cnticnt_i 表示 [u,v][u,v] 的最短路径上 ii 出现次数。那么这又变成了莫队的经典应用：查询跟区间内数字出现次数相关的权值。发现每次添加或减少一个数 xx，对答案的增或减都是 vx×wcntxv_x\times w_{cnt_x}，然后有修改操作，直接树上修改莫队即可。

不过要注意修改的时候，修改的那个点一定要在范围内才修改，这需要 stust_u 和 edued_u 仅有一个出现在区间内。

CF375D Tree and Queries

简单的树上莫队，不过一开始没有看清题意就做。因为是子树直接用 dfs 序即可，[l,r][l,r] 即 [dfnu,dfnu+sizeu−1][dfn_u,dfn_u+size_u-1]。不过求的东西不一样：出现次数 ≥k\geq k 的颜色个数，因此维护 cnticnt_i 表示 ii 出现次数，totitot_i 表示出现次数为 ≥i\geq i 的颜色个数，然后直接维护就好了，但是自己想复杂了，还是想清楚再做。

4. 回滚莫队

4.1. 简介

回滚莫队是一种支持只增不删或者只删不增的莫队，往往用来处理一些删除或是增加时间复杂度很大的题目。

4.2. 流程

回滚莫队分为两种，只删不增和只增不删。

4.2.1. 只删不增

  1. 和普通的莫队一样，以左端点所在块编号为第一关键字升序排列，右端点为第二关键字降序排列；

  2. 对于左右端点在同一个块中的询问，我们直接暴力计算，否则继续执行如下操作；

  3. 对于左端点在同一个块 xx 的询问，stxst_x 表示块 xx 第一个位置，我们先设一个初始的大区间 [stx,n][st_x,n]；

  4. 此时我们可以将一个询问分为两个部分：在左端点所在块中的；在左端点所在块外的。对于在左端点所在块外的，直接暴力移动右指针到询问的右端点，因为右端点是按降序排列的，所以只会进行删除操作；

  5. 对于在左端点所在块内的，先记录下此时的答案 tmptmp，以便后面的回溯操作。然后再移动左指针，因为左端点是按升序排列的， 因此也是只会进行删除操作；

  6. 然后再恢复左指针，答案回到 tmptmp，继续处理左端点在这个块的询问。

4.2.2. 只增不删

和上一种差别不大，只说一下不同的地方。

  1. 右端点为第二关键字升序排列；

  2. 对于左端点在同一个块 xx 的询问，edxed_x 表示块 xx 最后一个位置，我们先设一个初始的空区间 [edx+1,edx][ed_x + 1,ed_x]；

  3. 此时我们可以将一个询问分为两个部分：在左端点所在块中的；在左端点所在块外的。对于在左端点所在块外的，直接暴力移动右指针到询问的右端点，因为右端点是按升序序排列的，所以只会进行删除操作；

  4. 对于在左端点所在块内的，先记录下此时的答案 tmptmp，以便后面的回溯操作。然后再移动左指针，因为左端点是按升序排列的， 因此也是只会进行增加操作；

4.3. 原理

通过上面的流程，我们发现回滚莫队其实只是用一种操作来代替另一种操作，通过回溯答案来满足条件。

4.4. 例题

P4137 Rmq Problem / mex

发现 mex⁡\operatorname{mex} 在删除的时候很好求：直接于出现次数为 00 的 00 取 min⁡\min 即可，但增加非常麻烦，因此考虑只删不增的莫队。

AT1219 歴史の研究

像这种求权值最大值的，增加的时候很好求：直接于新增的权值取个 max⁡\max 即可，但删除的话非常麻烦，因此我们考虑只增不删的莫队。

5. 二次离线莫队

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

Powered by Gridea RSS