#创作计划# 莫队学习笔记

cjdst

2025-10-27 22:46:52

发布于：广东

96阅读

0回复

0点赞

UPD on 10.15：新增了一个不知名网站的一道题。
UPD on 10.1：新增了知名网站 Codeforces 的一道题。

嗯。

看到群友都学了莫队，所以我也浅学一下。

首先找 Q 群管家要了个代码，尝试自学。

他首先离线所有的询问，很正常。

然后看核心代码：

sort(q+1,q+Q+1,cmp);
l=1;
r=0;
cur=0;
for(i=1;i<=Q;i++)
{
	while(l<q[i].l)del(l++);
	while(l>q[i].l)add(--l);
	while(r<q[i].r)add(++r);
	while(r>q[i].r)del(r--);
	ans[q[i].id]=cur;
}

？？？？？？？？？？？？？？？？？？？？WTF

这玩意是怎么能过的？？？？？

肯定是排序暗藏玄机，看看：

bool cmp(query x,query y)
{
	if(x.l/block!=y.l/block)return x.l<y.l;
	return x.r<y.r;
}

嗯。。。啊？对吗？

哦对的对的。他这是按每个数左端点所处的块排序，所处的块相同再按右端点排序。然后查询就按照上一个的结果逐个改变左右端点递推处理。

左端点最多移动 $O(q\times \text{block})$ 次，右端点总共移动 $O(\frac{n^2}{\text{block}})$ 次，在 $n,q$ 同阶的情况下，当取 $\text{block}=O(\sqrt n)$ 时，总移动次数仅为 $O(n\sqrt n)$ 次。如果单次添加，删除的时间复杂度为 $O(1)$ 的话，总时间复杂度就是 $O(n\sqrt n)$ 。

甜菜啊！

当然， $n,q$ 不同阶的情况下可以考虑取 $\text{block}=\frac{n\sqrt q}{q}$ ，这样时间复杂度就是 $O(n\sqrt q)$ ，最优。

话不多说，直接洛谷找一个莫队蓝题做做。

P1494 小 Z 的袜子

显然，原问题可以转化成选取任意两个袜子颜色相同的方案数除以总方案数的结果。显然分母为 $\frac{(r-l+1)\times(r-l)}{2}$ ，问题的关键就在于如何求分子了。

注意到我们可以这样做：

开一个桶 $\text{bucket}$ ，记录区间内每个数记录的个数。

添加 $x$ ：答案增加 $\text{bucket}[x]$ ，然后使 $\text{bucket}[x]$ 增加 $1$ 。
删除 $x$ ：使 $\text{bucket}[x]$ 减小 $1$ ，然后使答案减小 $\text{bucket}[x]$ 。

然后写一下莫队就行了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int len;
struct query{
	int l, r, id;
	bool operator < (const query &b) const{
		if(l / len == b.l / len) return r < b.r;
		return l / len < b.l / len;
	}
}q[100005];
int a[100005];
int ans1[100005], ans2[100005];
int n, m;
int curl, curr;

int bucket[100005];
int cur;
void add(int idx){
	cur += (bucket[a[idx]]++);
}
void del(int idx){
	cur -= (--bucket[a[idx]]);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	len = sqrtl(n) + 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1);
	for(int i = q[1].l; i <= q[1].r; i++){
		add(i);
	}
	ans1[q[1].id] = cur, ans2[q[1].id] = (q[1].r - q[1].l + 1) * (q[1].r - q[1].l) / 2;
	curl = q[1].l, curr = q[1].r;
	for(int i = 2; i <= m; i++){
		while(curr < q[i].r) add(++curr);
		while(curr > q[i].r) del(curr--);
		while(curl > q[i].l) add(--curl);
		while(curl < q[i].l) del(curl++);
		ans1[q[i].id] = cur;
		ans2[q[i].id] = (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2;
	}
	for(int i = 1; i <= m; i++){
		if(ans1[i] == 0){
			cout << "0/1\n";
			continue;
		}
		int tmp = __gcd(ans1[i], ans2[i]);
		ans1[i] /= tmp, ans2[i] /= tmp;
		cout << ans1[i] << '/' << ans2[i] << '\n';
	}
	

	return 0;
}

时间复杂度： $O(n\sqrt n)$ 。

然后，我想到了一个更逆天的东西。

注意到树状数组可以当做集合， $O(\log n)$ 添加元素删除元素在线求第 $k$ 小。

树状数组+莫队=？区间第 $k$ 小！

那时间复杂度是多少呢？显然，是 $O(n\sqrt n\log n)$ 。注意到 $10^5\times \lceil\sqrt{10^5}\rceil\times \lfloor\log_2 10^5\rfloor=5.072\times 10^8$ ，只要常数够小甚至可以在 $1$ 秒内通过 $10^5$ 的数据！

理论存在，实践开始。

P3834 【模板】可持久化线段树 2，目标：80pts

思路已经讲的差不多了，直接贴代码。

注意值域，需要离散化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int len;
struct query{
	int l, r, k, id;
	bool operator < (const query &b) const{
		if(l / len == b.l / len) return r < b.r;
		return l / len < b.l / len;
	}
}q[200005]; 
int a[200005];
int b[200005];
int ans[200005];
int n, m;
int curl, curr;
int first[200005];
int tr[200005];
void add(int idx){
	for(int i = a[idx]; i <= n; i += (i & (-i))) tr[i]++;
}
void del(int idx){
	for(int i = a[idx]; i <= n; i += (i & (-i))) tr[i]--;
}
int query(int k){
	int cur = 0, ans = 0;
	for(int i = 17; i >= 0; i--){
		if(ans + (1 << i) > n) continue;
		if(cur + tr[ans + (1 << i)] >= k) continue;
		ans += (1 << i);
		cur += tr[ans];
	}
	return ans + 1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	len = sqrtl(n) + 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
	}
	for(int i = 1; i <= m; i++){
		cin >> q[i].l >> q[i].r >> q[i].k;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1);
	for(int i = q[1].l; i <= q[1].r; i++){
		first[a[i]]++;
	}
	for(int i = 1; i <= n; i++){
		tr[i] += first[i];
		if(i + (i & (-i)) > n) continue;
		tr[i + (i & (-i))] += tr[i];
	}
	ans[q[1].id] = query(q[1].k);
	curl = q[1].l, curr = q[1].r;
	for(int i = 2; i <= m; i++){
		while(curr < q[i].r) add(++curr);
		while(curr > q[i].r) del(curr--);
		while(curl > q[i].l) add(--curl);
		while(curl < q[i].l) del(curl++);
		ans[q[i].id] = query(q[i].k);
	}
	for(int i = 1; i <= m; i++){
		cout << b[ans[i]] << '\n';
	}

	return 0;
}

结果：挑战成功，甚至通过了该题。（绷）

实战演练，直接拿最近一场 Div3 的最后一题举例。

CF2149G Buratsuta 3

题意解析：给定一个数组 $A$ 和 $q$ 次询问，每次询问一个区间 $[l,r]$ ，请你输出 $[l,r]$ 中所有出现超过 $\frac{1}{3}$ 的数。

考虑莫队。

我们需要维护的内容如下：

$A_i$ 在区间内出现的次数。
出现次数为 $i$ 的数有哪些。
区间内有多少个出现超过 $\frac{1}{3}$ 的数。

显然可以用 set 通过添加和删除 $O(\log n)$ 维护，十分方便。

但是——注意数据范围， $n,q\le 2\times 10^5$ ，总时间复杂度就是 $O(n\sqrt n\log n)$ 的，在 $2\times 10^5$ 的数据下总运行次数约为 $1.6\times 10^9$ ，再叠加上 set 的大常数直接 T 飞了。我们需要更快速的数据结构。

我们可以使用一个冷门数据结构——list！它是用链表实现的，可以支持 $O(1)$ 在线插入、删除某个元素。

这时，我们需要的变量如下：

int times[n]：储存 $A_i$ 在区间内出现了多少次。
list <int> bucket[n]：储存出现次数为 $i$ 的数有哪些。
list <int>::iterator idxs[n]：迭代器，储存 $A_i$ 在 bucket 的哪个位置。
list <int> curans：储存区间内有多少个出现超过 $\frac{1}{3}$ 的数。
bool inans[n]：由于不是 set 不能自动去重，所以需要用一个数组储存 $A_i$ 是否已出现在答案中。

接下来就是折磨代码环节了。

// 这种题能写出大模拟也是没谁了 
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <list>
using namespace std;
int len;
struct query{
	int l, r, id;
	bool operator < (const query &b) const{
		if(l / len == b.l / len) return r < b.r;
		return l / len < b.l / len;
	}
}q[200005];
int a[200005], b[200005];
vector <int> ans[200005];
int n, m;
int curl, curr;
int curlen;

list <int> bucket[200005];
list <int>::iterator idxs[200005];
int times[200005];
bool inans[200005];
list <int> curans;

void add(int idx){// 添加元素
	bucket[times[a[idx]]].erase(idxs[a[idx]]);
	times[a[idx]]++;
	bucket[times[a[idx]]].push_back(a[idx]);
	auto it = bucket[times[a[idx]]].end();
	it--;
	idxs[a[idx]] = it;
	if(times[a[idx]] > curlen){
		if(!inans[a[idx]]){//不能自动去重所以得额外开个数组
			curans.push_back(a[idx]);
		}
		inans[a[idx]] = 1;
	}
	int newlen = (curr - curl + 1) / 3;
	if(curlen < newlen){
		curlen = newlen;
		for(int i:bucket[curlen]){
			for(auto it = curans.begin(); it != curans.end(); it++){// 我服了为什么list的erase还要迭代器
				if((*it) == i){
					curans.erase(it);
					inans[i] = 0;
					break;
				}
			}
		}
	}
}

void del(int idx){// 删除元素
	bucket[times[a[idx]]].erase(idxs[a[idx]]);
	times[a[idx]]--;
	bucket[times[a[idx]]].push_back(a[idx]);
	if(times[a[idx]] <= curlen){
		for(auto it = curans.begin(); it != curans.end(); it++){
			if((*it) == a[idx]){
				curans.erase(it);
				inans[a[idx]] = 0;
				break;
			}
		}
	}
	auto it = bucket[times[a[idx]]].end();
	it--;
	idxs[a[idx]] = it;
	int newlen = (curr - curl + 1) / 3;
	if(curlen > newlen){
		for(int i:bucket[curlen]){
			curans.push_back(i);
			inans[i] = 1;
		}
		curlen = newlen;
	}
}

void solve(){
	cin >> n >> m;
	len = n / (sqrtl(m) + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
	}
	for(int i = 1; i <= n; i++){
		bucket[0].push_back(i);
		auto it = bucket[0].end();
		it--;
		idxs[i] = it;
	}
	for(int i = 1; i <= m; i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1);
	curl = curr = q[1].l; 
	add(q[1].l);
	while(curr < q[1].r){
		add(++curr);
	}
	for(int i:curans) ans[q[1].id].push_back(b[i]);
	sort(ans[q[1].id].begin(), ans[q[1].id].end());
	
	
	for(int i = 2; i <= m; i++){
		while(curr < q[i].r) add(++curr);// 莫队核心操作
		while(curr > q[i].r) del(curr--);
		while(curl > q[i].l) add(--curl);
		while(curl < q[i].l) del(curl++);
		for(int j:curans) ans[q[i].id].push_back(b[j]);
		sort(ans[q[i].id].begin(), ans[q[i].id].end());// 懒得比较大小了
	}
	for(int i = 1; i <= m; i++){
        if(ans[i].empty()){
			cout << "-1\n";
			continue;
		}
		for(int j:ans[i]) cout << j << ' ';
		cout << '\n';
	}
	
	// 清空 
	for(int i = 1; i <= n; i++){
		a[i] = b[i] = 0;
		times[i] = 0;
		bucket[i].clear();
		inans[i] = 0;
	}
	for(int i = 1; i <= m; i++){
		q[i] = {0, 0, 0};
		ans[i].clear();
	}
	curans.clear();
	curl = curr = curlen = 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度 $O(\sum n\sqrt q)$ 。

结果：卡常失败，TLE on 5。

我常数大点怎么了555555555555555

注意到某个不知名网站新出了一个 APC（A*** Peak Contest），这场比赛中有一道题挺有意思的，并且可以使用莫队做，所以我就来写一篇题解。

题意解析：

给定一颗大小为 $n$ ，根为 $1$ 的树，树上的每个节点有一个颜色 $A_i$ ，给出 $q$ 次询问，每次询问一个节点，问它的子树中有多少种颜色出现次数 $\ge k$ 。

注意到一个节点的子树的 $\text{dfn}$ 是连续的，所以我们可以先随便 $\text{dfs}$ 一下，将 $A_{\text{dfn}_i}$ 变成 $A_i$ ，然后把问题转化成求区间有多少种颜色出现次数 $\ge k$ 。 $n,q\le 2\times 10^5$ 。

考虑莫队。

有个很显然的方法就是开一个 map 和一颗树状数组，然后 $O(\log n)$ 单点更新。

但是这样就和前面的区间第 $k$ 小的解法重复了，学不到任何新东西 ~~，而且还不好水创作计划~~。

我们可以新增一维 $k$ ，然后当作 $3$ 维莫队实现。

$3$ 维莫队的排序方式和 $2$ 维差不多：

先按第一维所在的块为第一关键字。
然后再按第二维所在的块为第二关键字。
最后按第三维作为第三关键字。

当然，为了卡常，我们可以分奇偶排序，减小移动次数。

这个时候，块长应该取多少合适呢？

没错，就是 $O(n^{\frac{2}{3}})$ ，这样第一维、第二维每次询问都得移动 $O(n^{\frac{2}{3}})$ 次，因为一共有 $O(n^2/(n^{\frac{2}{3}})^2)=O(n^{\frac{2}{3}})$ ，所以第 $3$ 维总共移动 $O(n\times n^{\frac{2}{3}})$ 次。总时间复杂度为 $O(n^{\frac{5}{3}})$ ，在 $n=2\times 10^5$ 时运行约 $6.8\times 10^8$ 次，足够了。

具体实现：

$\text{dfn}$ 转化：

int in[200005], out[200005];
int reala[200005];
int dfn;
void dfs(int cur, int fa){
	in[cur] = (++dfn);
	reala[dfn] = a[cur];
	for(int i:v[cur]){
		if(i == fa) continue;
		dfs(i, cur);
	}
	out[cur] = dfn;
}

单点加/删（由于不考虑大于等于 $0$ 的情况，所以 bucket2[0] 设什么值都不影响）：

void add_idx(int idx){
	int val = a[idx];
	bucket2[bucket[val]]--;
	bucket[val]++;
	bucket2[bucket[val]]++;
	if(bucket[val] == curk) curans++;
}
void del_idx(int idx){
	int val = a[idx];
	if(bucket[val] == curk) curans--;
	bucket2[bucket[val]]--;
	bucket[val]--;
	bucket2[bucket[val]]++;
}

$k$ 增加/减少 $1$ ：

void add_k(){
	curans -= bucket2[curk];
	curk++;
}
void del_k(){
	curk--;
	curans += bucket2[curk];
}

经过一番调试，我发现块长在 $400$ 左右时是最优的。跑了 300ms 不到的时间，可以看出这个 OJ 的评测速度是真的快。

总代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define int long long
using namespace std;
int len;
struct query{
	int l, r, k, id;
	bool operator < (const query &b) const{
		if(l / len == b.l / len){
			if(r / len == b.r / len){
                if(r / len % 2) return k > b.k;
                return k < b.k;
            }
			return r / len < b.r / len;
		}return l / len < b.l / len;
	}
}q[200005];
int a[200005];
int reala[200005];
vector <int> v[200005];
int ans[200005];
int in[200005], out[200005];
int n, m;

int dfn;
void dfs(int cur, int fa){
	in[cur] = (++dfn);
	reala[dfn] = a[cur];
	for(int i:v[cur]){
		if(i == fa) continue;
		dfs(i, cur);
	}
	out[cur] = dfn;
}

int curl, curr, curk;
int bucket[200005], bucket2[200005];
int curans;
void add_idx(int idx){
	int val = a[idx];
	bucket2[bucket[val]]--;
	bucket[val]++;
	bucket2[bucket[val]]++;
	if(bucket[val] == curk) curans++;
}
void del_idx(int idx){
	int val = a[idx];
	if(bucket[val] == curk) curans--;
	bucket2[bucket[val]]--;
	bucket[val]--;
	bucket2[bucket[val]]++;
}
void add_k(){
	curans -= bucket2[curk];
	curk++;
}
void del_k(){
	curk--;
	curans += bucket2[curk];
}
int query(){
	return curans;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	len = 350;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++){
		a[i] = reala[i];
	}
	for(int i = 1; i <= m; i++){
		int idx, val;
		cin >> idx >> val;
		q[i].l = in[idx], q[i].r = out[idx], q[i].k = val;
		q[i].id = i;
	}
	sort(q + 1, q + m + 1);
	curk = q[1].k;
	for(int i = q[1].l; i <= q[1].r; i++){
		add_idx(i);
	}
	curl = q[1].l, curr = q[1].r;
	ans[q[1].id] = query();
	for(int i = 2; i <= m; i++){
		while(curk < q[i].k) add_k();
		while(curk > q[i].k) del_k();
		while(curr < q[i].r) add_idx(++curr);
		while(curl > q[i].l) add_idx(--curl);
		while(curl < q[i].l) del_idx(curl++);
        while(curr > q[i].r) del_idx(curr--);
		ans[q[i].id] = query();
	}
	for(int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}
	

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 14

Zzzzzzsr（不处）
细节学术帖子发到灌水区

2025-10-01 来自广东
1
- cjdst
  回复
  Zzzzzzsr（不处）
  糖了
  
  2025-10-01 来自广东
  0
Xylophone
莫队和分块需要手动调块长吗（好奇）应该是赌跑不满

2025-10-27 来自广东
0
- cjdst
  回复
  Xylophone
  要的，因为不同的操作常数可能不一样，比如一到分块题处理小块常数是 $2$ ，大块是 $6$ ，那块长调成 $2\sqrt n$ 就是最优的
  
  2025-10-27 来自广东
  0
- cjdst
  回复
  Xylophone
  最后这题调端点的常数就是调 $k$ 的常数的六七倍
  
  2025-10-27 来自广东
  0
- Xylophone
  回复
  cjdst
  对于随机数据来说似乎用一些计算的奇技淫巧就可以给出非常数的较优块长
  
  2025-10-28 来自广东
  0
Xylophone
https://www.luogu.com.cn/problem/P3834水谷还不加数据？（bushi）
P2418这道纯粹的线段树因为神秘特性分块比贪心还快

2025-10-27 来自广东
0
- cjdst
  回复
  Xylophone
  绷
  
  2025-10-27 来自广东
  0
Xylophone
莫队大佬，orz

2025-10-27 来自广东
0
cjdst
d

2025-10-15 来自广东
0
𝓐𝓘𝓮𝓻
帅同，回个私信

2025-10-01 来自浙江
0
古希腊掌管AC和WA的神
%

2025-10-01 来自上海
0
༺ཌༀཉི༒白·羊༒༃ༀད༻
%%%大佬居然自学莫队吗？有点意思

2025-10-01 来自上海
0
氢氧化钠Ah
%%%

2025-09-30 来自四川
0
眼镜蛇
%%%

2025-09-30 来自江西
0
皮皮虾-逆蝶ND
d

2025-09-30 来自上海
0
皮皮虾-逆蝶ND
%

2025-09-30 来自上海
0
dream92143
%

2025-09-30 来自江苏
0
cjdst
d

2025-09-30 来自广东
0

P1494 小 Z 的袜子

P3834 【模板】可持久化线段树 2，目标：80pts

CF2149G Buratsuta 3

全部评论 14

d

热门讨论