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

AAA混凝土批发ppl哥

2025-10-01 16:41:21

发布于：广东

46阅读

0回复

0点赞

嗯。

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

首先找 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;
}