• 日期: 2026-11-11
  • 标签: 程序员

我的暴力有救了哈哈哈。

是什么

莫队是一种离线区间查询的算法，是前国家队队长莫涛提出并推广的。由离线+分块（排序）+暴力移动指针组成，简直就是优雅的暴力。

关于莫对的分类：目前有普通的只查询莫队、带修莫队（带修改的）、回滚莫队（用撤销操作来代替删除等修改）、以及树上莫队（树剖+其他的（带修\(\dots\)））和二次离线。

怎么实现

想要写代码，就要先知道这个算法的原理。

核心原理

莫队解决的问题通常有这样的特征：如果已知区间 \([L, R]\) 的答案，可以在很快（通常是 \(O(1)\)）的时间内，算出相邻区间（如 \([L-1, R]\) 或 \([L, R+1]\)）的答案。
其实就是区间查询，只是莫队算法的核心做法就是：把所有询问离线，按某种顺序排序，然后暴力移动左右指针，让指针总移动距离尽可能小。

代码思路

那我们就按照 离线+排序+暴力移指针 的顺序写。

离线很简单，就是把所有询问按照 \([l,r,id]\) 的方式存起来，至于为什么 \(id\)，因为后面的排序会把顺序打乱，需要存一下顺序，不然输出会 WA。

那具体是哪种排序方式呢？
当然不是只按左/右中一个，如果题目要求问的跨度很大，那不就又退化成 \(O(n^2)\) 了吗。

那么就要请到分块出场了。
分块的作用就是控制左右指针的移动总量。具体做法是：

  • 把序列下标 \(1\sim n\) 分成一些长度为 \(\sqrt{n}\)（或 \(n^{\frac{2}{3}}\)） 的块
  • 对询问排序时，先按左端点所在的块编号升序，同一块内再按右端点排序（右端点可以配合奇偶性优化）。

这时的时间复杂度大概就是 \(O(n\sqrt{n})\)，比暴力快多了 （难怪叫优雅的暴力）。

排序时可以加上同块内的右指针奇偶性的优化。就是对于同一个块内的奇数右指针按升序排，偶数右指针按降序排，这样右指针的移动就是"Z"字形的。

这有什么好处

这样就可以使右指针的移动具有单调性，效率更高。
如图：
image

最后是暴力移动指针。
其实就是维护一个当前区间，通过一步步移动左右指针，让它变成下一个要查询的区间，并在移动过程中更新答案。
由于排过序，指针移动的总距离被大大缩短了。

对于转移到下一个区间，一共有四种情况（左右节点总共）。

  1. 当前的 \(l>\) 下一个的 \(l\)，那么缩小（当前的区间更小）\(l\)；
  2. 当前的 \(r<\) 下一个的 \(r\)，那么扩大（同上）\(r\)；
  3. 当前的 \(l>\) 下一个的 \(l\)，那么扩大（当前的区间更大）\(l\)；
  4. 当前的 \(r>\) 下一个的 \(r\)，那个缩小（同上）\(r\)。

有点难理解，我当时都记混了。

图片帮助理解

image

具体实现

主要框架就是这样，其余要添加的操作有需要看题了。

普通莫队

PID：P2709

思路就是把询问按左端点分块、块内按右端点排序（普通莫队），双指针移动时 \(O(1)\) 增量维护每种颜色计数的平方和 sum（add/del 先减旧平方再加新平方），离线存答案按原编号输出。

$\color{Cyan}Code$ 
#include
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,k,a[N],b,ans[N],sum,c[N];
struct block{
	int l,r,op;
	bool operator<(const block &k)const{//排序优化
		if(l/b!=k.l/b) return lk.r;
	}
}q[N];
void add(int x){sum-=c[x]*c[x],c[x]++,sum+=c[x]*c[x];}
void del(int x){sum-=c[x]*c[x],c[x]--,sum+=c[x]*c[x];}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	b=sqrt(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,l,r;i<=m;i++){
		cin>>l>>r;
		q[i]={l,r,i};
	}
	sort(q+1,q+m+1);
	for(int i=1,l=1,r=0;i<=m;i++){
		while(l>q[i].l) add(a[--l]);
		while(rq[i].r) del(a[r--]);
		ans[q[i].op]=sum;
	}
	for(int i=1;i<=m;i++) cout<

带修莫队

PID：P1903

这就是带修改的莫队。

1. 三维莫队：区间 + 时间
普通莫队只有 \(l,r\) 两个指针；这题多了修改，就引入第三个指针 \(t\) 记录已执行的修改次数。每个询问记录它发生时的 \(t\)，状态变成 \((l,r,t)\)。按 l 所在块、r 所在块、t 三维排序，块长取 \(n^{\frac23}\)，复杂度 \(O(n^{\frac53})\)。

2. 时间指针的前进与回退
移动 \(l,r\) 时照常 add/del 维护颜色计数和种数；移动 \(t\) 时执行/撤销修改：若修改位置 p 在当前区间内，就先 del 旧色再 add 新色，否则不动答案。前进用 ++x，回退用 x--，两段 while 对称写。

3. 用 swap 让修改可撤销
swap(a[p], re[x].c) 应用修改的同时把旧颜色存回 re[x].c，回退时再 swap 一次就还原。区间外的位置也要 swap（只是不更新答案），否则状态会错乱。这是带修莫队最核心的技巧。

$\color{Cyan}Code$ 
#include
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,cntq,cntr,a[N],b,ans[N],sum,c[N];
struct block{
	int l,r,t,op;
	bool operator<(const block &k)const{
		if(l/b!=k.l/b) return l>n>>m;
	b=pow(n,0.66);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,l,r;i<=m;i++){
		char s;
		cin>>s>>l>>r;
		if(s=='Q') q[++cntq]={l,r,cntr,cntq};
		else re[++cntr]={l,r};
	}
	sort(q+1,q+cntq+1);
	for(int i=1,l=1,r=0,x=0;i<=cntq;i++){
		while(l>q[i].l) add(a[--l]);
		while(rq[i].r) del(a[r--]);
		while(xq[i].t){//时间戳变小，还原，其余同上 
			int p=re[x].p;//找到当前时间x对应的修改操作，到要改的位置p 
			if(l<=p&&p<=r) del(a[p]),add(re[x].c); 
			swap(a[p],re[x--].c);//x--是让时间倒流一步。
		}
		ans[q[i].op]=sum; 
	}
	for(int i=1;i<=cntq;i++) cout<

回滚莫队

PID：P14420

1. 矛盾：增加容易，删除难
维护 事件类型 × 出现次数 的最大值。加入一个元素时，只需拿 \(c _x\times k_x\) 更新答案，很容易；但删除时无法快速知道最大值是否变化，所以不能用普通莫队。

2. 回滚莫队：只加不减
按左端点分块，块内询问按右端点升序。对每块固定一个基准右边界 rl，右指针只向右扩展（只加）；左指针临时向左扩展来覆盖询问，算完答案后把左指针移回 rl 并撤销计数（回滚），从而避免任何删除操作。

3. 块内暴力 + 保存/恢复 res
\(l、r\) 同块的询问直接暴力算（块长 \(\sqrt n\)）；跨块询问先用 \(lst\) 保存右扩展后的答案，临时扩展左指针得到 \(res\) 输出，回滚时 \(res=lst\) 恢复，保证下一询问从干净状态开始。

$\color{Cyan}Code$ 
#include
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N],c[N],lst,res,ans[N],b,bl[N],k[N],t[N];
struct block{
	int l,r,op;
	bool operator<(const block &b)const{
		if(bl[l]!=bl[b.l]) return l>n>>m;
	b=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i],k[i]=a[i];
		bl[i]=(i-1)/b+1;
	}
	int num=bl[n];
	sort(k+1,k+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(k+1,k+n+1,a[i])-k;
	for(int i=1,l,r;i<=m;i++) cin>>l>>r,q[i]={l,r,i};
	sort(q+1,q+m+1);
	for(int i=1,x=1;i<=num;i++){
		res=lst=0;
		for(int j=1;j<=n;j++) c[j]=0;
		int rl=min(b*i,n),l=rl+1,r=rl;
		for(;bl[q[x].l]==i;++x){
			if(bl[q[x].l]==bl[q[x].r]){
				ans[q[x].op]=calc(q[x].l,q[x].r);
				continue;
			}
			while(rq[x].l) add(a[--l]);
			ans[q[x].op]=res;
			while(l<=rl) --c[a[l++]];//回滚
			res=lst;
		}
	}
	for(int i=1;i<=m;i++) cout<
为什么要回滚 $l$?

为了“撤掉临时加的东西”。
只有右指针扩展出来的部分是真正属于莫队当前状态的。
左指针向左扩展只是为了算当前这一个询问的答案，它是“临时借用的”。

树上莫队

PID：P4074

实质上就是树+带修莫队，所以只需要写个树剖+带修莫队就行了。
对于树剖后的操作，需要判断这是的查询是否是在同一条直的链上，因为在同一条链上好处理；而不再同一条链上就不好处理了，因为这是一条"折链"，还需要计入两个点的 LCA 的。

  • 欧拉序（括号序）代替DFS序：这里求树剖的 in 和 out 是为了构建长度为 2n 的欧拉序（每个点进树记一次，出树记一次），而不是求普通的子树连续区间。利用 flg[x] ^= 1 的异或性质：出现两次代表该点不在路径上（进+出抵消），出现一次代表该点在路径上。
  • 直链与折链的处理：
    • 直链（lca(x,y)==x）：对应的莫队区间就是 [in[x], in[y]]。
    • 折链（lca(x,y)!=x）：对应的莫队区间是 [out[x], in[y]]。注意这里，此时 LCA 并没有被包含在区间内，所以要把 LCA 记录下来（代码里的 q[i].f = lca），在莫队统计完该区间的答案后，单独把 LCA 的贡献加进去。
  • 时间指针的移动（带修部分）：遇到修改操作时，需判断被修改的点是否在当前莫队区间内（flg[pos] == 1）。如果在，就先删除旧颜色的贡献，用 swap 换上新颜色，再加上新颜色的贡献；如果不在，直接 swap 换色即可，不影响当前答案。
  • 贡献计算与排序：每次加入/删除点，更新该颜色的出现次数 cnt，贡献由 w[cnt[c]] * v[c] 动态维护。排序用三维关键字 (l所在块, r所在块, t)，块长取 (2n)^{2/3}。

一句话：用树剖欧拉序把树上路径映射成序列区间（折链单独补 LCA 贡献），然后套用带修莫队，时间指针移动时判断点是否在区间内来变更颜色。

$\color{Cyan}Code$（有点长，慎入） 
#include
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,k,b,t,tot,sum,v[N],w[N],c[N],pos[N],nc[N],cnt[N],ans[N];
struct block{
	int l,r,t,op,f;
	bool operator<(const block &k)const{
		if(l/b!=k.l/b) return l g[N];
void dfs1(int u,int f){
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	for(auto v:g[u]){
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]>n>>m>>k;
	for(int i=1;i<=m;i++) cin>>v[i];
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1,u,v;i>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1,t=0,op,x,y;i<=k;i++){
		cin>>op>>x>>y;
		if(op==1){
			int f=lca(x,y);
			q[++tot].t=t,q[tot].op=tot;
			if(in[x]>in[y]) swap(x,y);
			if(f==x) q[tot].l=in[x],q[tot].r=in[y];//直链
			else q[tot].l=out[x],q[tot].r=in[y],q[tot].f=f;//折链
		}
		else pos[++t]=x,nc[t]=y;
	}
	b=pow(n<<1,0.66);
	sort(q+1,q+tot+1);
	for(int i=1,l=1,r=0,x=0;i<=tot;i++){
		while(l>q[i].l) add(a[--l]);
		while(rq[i].r) add(a[r--]);
		while(xq[i].t){
			if(flg[pos[x]]){
				add(pos[x]);
				swap(c[pos[x]],nc[x]);
				add(pos[x]);
			}
			else swap(c[pos[x]],nc[x]);
			x--;
		}
		ans[q[i].op]=sum;
		if(q[i].f) ans[q[i].op]+=1*w[cnt[c[q[i].f]]+1]*v[c[q[i].f]];
	}
	for(int i=1;i<=tot;i++) cout<

小TIPS

说了这么多，还是得说说细节，不然很容易写炸。

保留一～六，已将所有数学公式统一改为 $ 包裹，分数改为 \frac{}{} 格式：

一、 判断能不能用莫队

  1. 必须能离线：莫队本质是调整询问顺序，强制在线（如异或加密查询）不能用。
  2. 必须能 \(O(1)\) 或 \(O(\log n)\) 增量更新：区间向外扩或向内缩一步时，答案必须能快速更新。如果“加”容易“删”难，想回滚莫队（如 P14420）；如果“加”难“删”容易，想只删莫队。

二、 指针移动的“玄学”与细节

  1. 初始区间设为空：通常写 l = 1, r = 0（或者 l = rl+1, r = rl），保证一开始区间为空，避免多算。
  2. 四个 while 的顺序无所谓，但别写错边界：
    while (l > ql) add(a[--l]); // 左指针外扩，先移位再加
while (r < qr) add(a[++r]); // 右指针外扩，先移位再加
while (l < ql) del(a[l++]); // 左指针内缩，先删再移位
while (r > qr) del(a[r--]); // 右指针内缩，先删再移位

三、 排序与块长的玄学

  1. 块长不要死记 \(\sqrt{n}\)：
    • 普通莫队：大多都是 \(\sqrt{n}\)。
    • 带修莫队：\(n^{\frac{2}{3}}\)（pow(n, 0.66)），因为多了一维时间。
    • 树上莫队：序列长度是 \(2n\)，所以块长是 \(\sqrt{2n}\) 或 \((2n)^{\frac23}\)。
  2. 奇偶化排序（常数优化）：对于普通莫队，右端点可以写成“奇数块升序，偶数块降序”：
    if((l/b)&1) return rk.r;
    能让右指针少跑很多冤枉路。
  3. 带修莫队的排序一定要多判一层：
    if(l/b!=k.l/b) return l

四、 修改与撤销（带修莫队专属）

  1. 修改用 swap 实现可逆：swap(a[pos], mod[x].c) 是带修莫队的灵魂。走时间前进时 swap 存下旧值，走时间回退时再 swap 还原。
  2. 判断位置是否在区间内：时间指针移动时，一定要判断 l <= pos && pos <= r（或树上 flg[pos] == 1）。不在区间里的修改不影响答案，但依然要 swap，不然回退时状态全乱。

五、 树上的特殊处理

  1. 欧拉序中一个点出现两次：利用 flg ^= 1，进和出相遇抵消，剩下的就是路径上的点。
  2. 折链必补 LCA：对于 [out[x], in[y]] 这种区间，LCA 绝对不在区间内。最后算完莫队答案，记得把 LCA 的贡献单独加一次（加的时候要考虑 cnt[颜色]+1 的权值）。

六、 回滚莫队专属坑点

  1. 左指针的“家”是固定的：每一块处理时，左指针必须从块右边界 R+1 出发，临时往左扩，算完必须滚回 R+1，并用 res = last 强行恢复答案。
  2. 同块询问直接暴力：如果询问的左右端点在同一块里（bl[l] == bl[r]），区间长度不到 \(\sqrt{n}\)，直接 \(O(\sqrt{n})\) 暴力扫，写起来比强行回滚简单得多。
"

原文地址: https://www.cveoy.top/t/topic/qHWg 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录