Update 2026.1

Update 2025.3.5 : Luogu博客需要科技才能访问，无奈只能搬运一下，这是之前的入门学习材料

---

莫队算法是一种可以解决大部分区间离线算法的离线算法，核心思想是分块。 一般情况下时间复杂度为 $O(n\sqrt{n})$ ,超好写，是解决问题的很优雅的暴力方法。（当然毒瘤出题人也会卡莫队，比如强制在线，或复杂度 $TLE$）

普通莫队

问题引入

假如有这样一道题：对于一个数列，每次给出一个询问 $L,R$ ，求 $[L,R]$ 的区间和。（强制使用莫队来做）

【分析】

假设你现在已经知道区间 $[2,5]$ 的区间和，求区间 $[2,6]$ 区间和，怎么求？显然只需要在 $[2,5]$ 的基础上加上第 $6$ 项的贡献。求区间 $[3,6]$ 的区间和，可以在区间 $[2,5]$ 和的基础上，加上第 $6$ 项的贡献，减去第 $2$ 项的贡献，也就是当前区间的值是上一步区间左右端点一步一步挪动过去的。

对于当前区间 $[L,R]$ ，可以分四种情况讨论挪动过程

• 1.加上当前区间左边一格的贡献：$Add(--L)$

• 2.加上当前区间右边一格的贡献：$Add(++R)$

• 3.减去当前区间左边一格的贡献：$Sub(L++)$

• 4.减去当前区间右边一格的贡献：$Sub(R--)$

注意：区间先扩大，再缩小，想一想为什么？（防止 $L>R$）

当时这样做显然会超时，时间复杂度是 $O(n*m)$

如果我们询问的顺序如下：

$[1,2],[n-1,n],[1,2],[n-1,n],[1,2],[n-1,n],\dots$

时间复杂度 $O(nm)$，显然 TLE

但是如果修改一下询问顺序：

$[1,2],[1,2],[1,2],[n-1,n],[n-1,n],[n-1,n]...$

效率就会大大不同，也就是询问顺序会影响时间复杂度

莫涛大佬套了分块，通过巧妙安排询问顺序，优化了时间复杂度。

排序规则

对于一个询问 $[L,R]$ ，对于 $L$ 按照其所在块排序，对于 $L$ 在同一块内的，按照 $R$ 的大小排序。

即第一关键字是 $L$ 所在块，第二关键字是 $R$。

莫队主体框架是一样的，区别在于 $Add$ 和 $Sub$ 函数

主体框架

int a[N],n,m,k,cnt[N],len;
ll res,ans[N];
struct node{
	int l,r,id;
}q[N];
cin>>n>>m>>k;
len=sqrt(n);  //块长
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,cmp);  //按照规则排序
int l=1,r=0;
for(int i=1;i<=m;i++)
	{
		while(q[i].l<l)add(--l);
		while(q[i].r>r)add(++r);
		while(q[i].l>l)sub(l++);
		while(q[i].r<r)sub(r--);
		ans[q[i].id]=res;  //保留答案
	}
for(int i=1;i<=m;i++)
	cout<<ans[i]<<endl;

自定义排序

自定义函数修改如下：

bool cmp(node a,node b)
{
	return (a.l/len==b.l/len)?(a.r<b.r):(a.l<b.l);
} 

复杂度分析

序列长度为 $n$，询问次数为 $m$，设块长为 $L$，分成 $\frac{n}{L}$ 块。

• 1.右端点 $curR$ 的移动总次数：$O(\frac{n^2}{L})$

  排序后，同一左块内的所有查询，右端点是升序排列的（第二关键字升序），因此对每个块，右端点 $curR$ 移动总长度为 $O(n)$ , 总共有 $\frac{n}{L}$ 个块，那么总移动次数就是 $O(\frac{n^2}{L})$。

• 2.左端点 $curL$ 的移动总次数: $O(mL)$

  排序后，查询按左块升序排列，分两种情况分析 $curL$ 移动：

  同一块内的查询：左端点 $curL$ 都在同一个大小为 $L$ 的块内，因此处理该块内所有查询时，$curL$ 最多在块内移动 $L$ 次（从块的一端到另一端），单次块内 $curL$ 移动次数上界为 $O(L)$；

  跨块的查询：从第 $k$ 块的查询切换到第 $k+1$ 块的查询时，$curL$ 最多从第 $k$ 块的任意位置移动到第 $k+1$ 块的任意位置，移动次数仍为 $O(L)$（块大小为 $L$）； 总共有 $m$ 个查询，所有情况的 $curL$ 单次移动均不超过 $L$，因此整体移动总次数上界为：$O(m⋅L)$。

那么总时间复杂度为：

$O(\frac{n^2}{L}+Lm)$ ，根据不等式，当 $\frac{n^2}{L}=Lm$ 时不等式区最小值，此时 $L=\frac{n}{\sqrt{m}}$ ，时间复杂度为 $O(n\sqrt{m})$ 。

当 $n$ 与 $m$ 数量级相同，$L=\sqrt{n}$ ,时间复杂度为 $O(n\sqrt{n})$

其他情况，块长应取 $L=\frac{n}{\sqrt{m}}$

奇偶优化

对于所有询问，为了减少 $R$ 无用移动，当 $L$ 所在的块是奇数时按照 $R$ 从小到大，否则从大到小排序。

这是一种常数优化，并不影响时间复杂度。

如果加上奇偶优化，排序函数如下：

bool cmp(node a,node b)
{
    if(a.l/len==b.l/len)return (a.l/len&1)? a.r>b.r : a.r<b.r;
    return a.l<b.l;
}

---

几何解释

每一个询问 $[l,r]$ 可以看作在二维平面上的一个点，从一个询问到另外一个询问，相当于两个点之间的曼哈顿距离。

如果按照横坐标对所有询问进行排序，访问顺序如下图，时间复杂度是 $O(mn)$。

按照左端点所在块访问，块内按照右端点排序，访问顺序如下：

如果带上奇偶优化，访问顺序如下：

---

例1. P3901 数列找不同

【题意简化】给定一个长度为 $n$ 的整数序列 $A_i$，$q$ 次询问，询问区间 $[l,r]$ 内所有数是否互不相同。$(1\le n,q\le 10^5,1\le A_i \le n)$

【分析】莫队基础题。利用计数数组，记录每个数在询问区间出现的次数，所有询问按照莫队方式离线排序。当一个数需要加入计数数组和重复的种类数 cnt，若计数个数从 1 增加为 2 ，说明此时有 2 个相同的数，重复种类数 cnt加 1 。当删除一个数 ，若计数个数从 2 减 1 ,说明此时这个数，从重复到不重复，cnt 减少 1 。从一个询问区间移动到另外一个询问区间，cnt 如果为 0 ，说明此询问区间没有相等的数，否则有相等的数。

【参考代码】点击

例2. SP3267 DQUERY - D-query

【题意简化】给定 $n$ 个整数 $a_i$ , $q$ 次询问，询问区间 $[l,r]$ 内有多少不同的数字。$(1 \le n \le 3\times 10^4,1 ≤ q ≤ 2\times 10^5, 1\le a_i \le 10^6)$

【分析】对所有询问离线排序。定义一个全局计数数组，记录值为 $a_i$ 出现的次数。增加数时，若计数次数从 $0$ 增加到 $1$ ,说明增加了一个不同的数字，答案加 $1$ ；当删除一个数时，若计数次数从 $1$ 减少到 $0$ ，说明减少了一个不同的数字，答案减 $1$。

本题是弱化版HH的项链,“HH的项链”数据加强，莫队会超时，可以利用这个题目学习莫队入门。

【参考代码】点击

例3. P2709 【模板】莫队 / 小B的询问

【题意简化】给定一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。 $m$ 次询问，每个询问给定一个区间 $[l,r]$，求：

$$\sum\limits_{i=1}^k c_i^2$$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。

$1\le n,m,k \le 5\times 10^4$

【分析】莫队的经典板子题，增加或减掉一个点，那么就减掉之前的贡献，加上新贡献。

增加一个数 $x$ ,那么对答案的贡献增加 $cnt^2_x-(cnt-1)^2_x$。同理减少一个数去掉减少对答案的贡献。

void add(int x)
{
	cnt[a[x]]++;
	res+=(cnt[a[x]]*cnt[a[x]])-(cnt[a[x]]-1)*(cnt[a[x]]-1);
}
void sub(int x)
{
	cnt[a[x]]--;
	res-=(cnt[a[x]]+1)*(cnt[a[x]]+1)-(cnt[a[x]]*cnt[a[x]]);
}

【参考】：点击

例4. [ABC293G] Triple Index

【题意简化】给定一个长度为 $N$ 的正整数序列 $(A_1,\ A_2,\ \ldots,\ A_N)$，以及关于该序列的 $Q$ 个查询。

对于每个 $q = 1, 2, \ldots, Q$，第 $q$ 个查询给出一对整数 $(l_q,\ r_q)$，请输出满足以下两个条件的整数三元组 $(i,\ j,\ k)$ 的个数：

• $l_q \leq i < j < k \leq r_q$
• $A_i = A_j = A_k$

数据规模： $1 \leq N ,Q ,A_i\leq 2 \times 10^5$

【分析】如果增加一个数 $x$, 计数个数从 $cnt$ 个变为 $cnt+1$ ，对答案贡献增加：

$C^3_{cnt+1}-C^3_{cnt}=\frac{cnt*(cnt-1)}{2}$

同理减少一个数，从 $cnt$ 个变为 $cnt-1$，对答案减少：

$C^3_{cnt}-C^3_{cnt-1}=\frac{(cnt-1)*(cnt-2)}{2}$

【参考代码】点击

例5. P1494 小Z的袜子

【题意简化】给定一个长度为 $N(\le 50000)$ 的序列，多次询问 $[l,r]$ 任意抽中两个相同的数概率。

【分析】对所有操作进行分块，也就是莫队。

单点移动需要计算，区间 $[l,r]$ 总共的方法数为 $C_{r-l+1}^2$。

抽中相同的方法数为 $sum$，$col[x]$ 表示 $x$ 的个数。

当新增 $x$ , 抽中相同的方法数 $col[x]\to col[x]+1$ ，那对答案的增量就是 $C_{col[x]+1}^2-C_{col[x]}^2=col[x]$ , 那 $sum+=col[x]$,然后 $col[x]++$.

当删除 $x$ ,那抽中相同的方法数 $col[x]\to col[x]-1$, 那减少量就是 $C_{col[x]}^2-C_{col[x]-1}^2=col[x]-1$ . 先 $col[x]--$， 相同的方法数 $sum-=col[x]$.

【参考代码】点击

例6. CF617E XOR and Favorite Number

【题意简化】给定一个长度为一个长度为 $n$ 的数组 $a_{i}$ 和整数 $k$ 。现在他要求你回答 $m$ 个询问。每个询问由一对 $l_{i}$ 和 $r_{i}$ 给出，问你在区间 $l \leq i \leq j \leq r$ 内，有多少组整数对 $(i,j)$，使得数列 $a_{i}, a_{i+1}, \ldots, a_{j}$ 的异或和等于 $k$。

$1 \leq n, m \leq 10^5$，$0 \leq a_i,k \leq 10^6$

【分析】对于 $a_{i}, a_{i+1}, \ldots, a_{j}$ 可以使用前缀异或和表示 $s_{j}\oplus s_{i-1}$ 。

对于新增位置 $p$ , 以 a[p] 结尾考虑 区间 [j,p] 异或和表示为 $s_p\oplus s_{j-1}=k$ ,可以表示为 $s_{j-1}=k\oplus s_p$ ，即只需要知道有多少个前缀和等于 $k \oplus s_p$ ,就可以计算出以 a[p] 为结尾的符合条件的子数组。注意 $s_{j-1}=k\oplus s_p$ ,那么计数要算完后再增加。

同理，对于减少位置 $p$ , 对于区间 [p,j] ,去掉 $s[p]$ 的贡献，区间 [p,j] 的区间和 $s_{p-1}\oplus s_j=k$，表示为 $s_{j}=k\oplus s_{p-1}$，需要知道有多少个 $k\oplus s_{p-1}$ ,那么对于询问区间 l-1.

【参考代码】点击

例7. P5268 [SNOI2017] 一个简单的询问

【题意简化】

给你一个长度为 $N$ 的序列 $a_i$，$1\leq i\leq N$，和 $q$ 组询问，每组询问读入 $l_1,r_1,l_2,r_2$，需输出

$$\sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x)$$

$\text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中，数字 $x$ 出现了多少次。

$N,Q\leq 50000$，$1\leq a_i\leq N$，$1\leq l_1\leq r_1\leq N$，$1\leq l_2\leq r_2\leq N$

【分析】对于 $get(l_1,r_1,x)$ 可以表示为 $get(1,r_1,x)-get(1,l_1-1,x)$. 记 $get(1,r1,x)$ 为 $P(r1,x)$ , 那么可以得到

$$\sum{get(l_1,r_1,x)get(l_2,r_2,x)}=\sum {(P(r_1,x)-P(l_1-1,x))*(P(r_2,x)-P(l_2-1,x))}=\sum(P(r_1,x)*P(r_2,x)-P(r_1,x)*P(l_2-1,x)-P(l_1,x)*P(r_2,x))+P(l_1-1,x)*Pl_2-1,x)$$

将每个询问分成 $4$ 部分，考虑每个数出现次数在 $[1,l]$ 与 $[1,r]$ 出现次数的乘积。使用两个计数数组 cntl[x] 和 cntr[x] 分别表示 x 在 [1,l] 和 [1,r] 中出现的次数. 考虑 $r$ 移动增加贡献，对于 [1,r] 计数数组 cntr[a[r+1]]++ ,对结果贡献是 [1,l] 出现的次数，结果增加 cntl[a[r+1]]，同理减少。

时间复杂度 $O(n\sqrt{n})$ ，本题还可以直接分块做，可以思考如何分块解决。

【参考代码】点击

---

其他题目

CF86D Powerful array

P3604 美好的每一天

---

其他莫队算法：带修莫队、树上莫队、二次离线、回滚莫队

---

学习完毕

{{ select(1) }}

• YES
• NO