专栏文章

浅谈回滚莫队

BBFqwqYoshino
算法·理论参与者 22已保存评论 27

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
27 条
当前快照
1 份
快照标识符
@mhz5rxrj
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文

回滚莫队

前置知识：莫队。
不会的同学可以看往期日报
回滚莫队，听起来好像很高级的样子。
但其实，它还有个很平凡的名字——不删除莫队。
回顾普通的莫队，其实说到底一共只有四个操作，分别是 l++,l−−,r++,r−−l++,l--,r++,r--。
而这些操作实际上又分成两大类，分别是插入和删除。
简单的说，当我们执行完 l−−l-- 或是 r++r++ 的操作后，我们的区间变长了，相当于我们向区间内插入了一个数。
而另外两个操作之后呢，我们的区间变短了，相当于我们从区间中删除了一个数。
虽然在平时的莫队中，这两者的复杂度是一样的，但显然，删除的操作往往更为复杂，甚至有的时候我们能很简单的完成插入操作，但却一直想不到如何进行删除。这个时候，我们的回滚莫队就要登场了。
我们先通过一个比较简单的例子来了解一下回滚莫队。

区间众数问题

给定一个序列以及若干次询问，求区间众数，可离线。
这个问题是个经典的问题，目前有许多的解法。但从思维难度上来讲，回滚莫队可能是最简单的。
考虑莫队。我们维护一个 ff 数组代表出现次数，当我们要插入一个数时，我们只需要更新这个数的次数，然后和最大值作比较。这是大家都能想到的。
但要删除一个数就显得比较复杂，于是我们可以对莫队作一点变化。
首先，对于左右端点位于一个块内的询问，我们直接暴力，这样的复杂度显然正确。
接着，我们依然按照左端点排序，将左端点在同一个块内的数拿出来一起处理。
我们直接将右指针移到该左端点所在块的右端点处，然后暴力向右插入。这样，在块外的部分的贡献我们就可以统计了。
然后我们将状态保存，然后将左指针移到左端点所在块的右端点 +1+1 处，向左插入，将块内的部分的贡献加入。
然后，我们再将左端点逐个移回，并撤销左区间的贡献即可。注意这里是撤销，而不是删除。
具体的实现方法很多，比如我们在右端点时将区间众数答案保存（定义一个变量 lst=anslst=ans），然后左端点插入时修改 ff 数组，撤回时依然修改 ff 数组，然后将答案变回（ans=lstans=lst）。
这样，我们的 ff 数组和 ansans 最终都没有发生变化，而左指针又回到了左端点所在块的右端点 +1+1，就好像什么也没有发生。
右端点的复杂度之和显然是 O⁡(nn)\operatorname O(n\sqrt n)，和莫队相同。而左端点由于每次的移动不超过 n\sqrt n，顾复杂度为 O⁡(mn)\operatorname O(m\sqrt n)。因此，莫队的复杂度没有发生任何变化。
以上就是回滚莫队的基本内容，通过巧妙的变换莫队的指针位置来避免了删除操作。
当然实际上我们也可以类似的弄一个不插入莫队（这个名字是自己取的qaq），但由于一般很少见到插入比删除麻烦的题，所以实际作用不大。
下面我们来做几道题练练手。

AT1219 歴史の研究

https://www.luogu.com.cn/problem/AT1219
实际上，这个题和区间众数的区别不是很大，只不过是在更新答案的时候再乘以一个 XiX_i。
和区间众数一样，我们维护一个数的出现次数。然后跑回滚莫队。更新答案时用事件的发生次数乘以重要度，与目前答案取最大值作为答案。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
char cr[200];int tt;
inline void print(int x,char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=1e6+10;
const int blk=405;
int n,a[maxn],m,bl[maxn],cnt[maxn];
int L[maxn],R[maxn],ans[maxn],mx,lst;
int lsh[maxn],len,c[maxn],del;
bool flag=0;
struct query{
	int l,r,id;
	friend bool operator <(query c,query d){
		if(bl[c.l]==bl[d.l]) return c.r<d.r;
		return c.l<d.l;
	}
}q[maxn];
int chk(int l,int r){
	mx=0;
	for(int i=l;i<=r;i++){
		cnt[c[i]]++;
		mx=max(a[i]*cnt[c[i]],mx);
	}
	for(int i=l;i<=r;i++) cnt[c[i]]--;
	return mx;
}
signed main(){
	n=read();m=read();
	int lxl=1;
	L[1]=1;
	while(L[lxl]+blk<n){
		R[lxl]=L[lxl]+blk-1;
		lxl++;
		L[lxl]=R[lxl-1]+1;
	}
	R[lxl]=n;
	for(int i=1;i<=lxl;i++){
		for(int j=L[i];j<=R[i];j++){
			bl[j]=i;
		}
	}
	for(int i=1;i<=n;i++){
		a[i]=lsh[i]=c[i]=read();
	}
	sort(lsh+1,lsh+n+1);
	len=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++)
		c[i]=lower_bound(lsh+1,lsh+len+1,c[i])-lsh;
	for(int i=1;i<=m;i++){
		q[i].l=read();q[i].r=read();q[i].id=i+del;
		if(bl[q[i].l]==bl[q[i].r]){
			ans[i+del]=chk(q[i].l,q[i].r);
			i--,m--,del++;
		}
	}
	sort(q+1,q+m+1);
	int l,r;
	for(int i=1;i<=m;i++){
		if(bl[q[i].l]!=bl[q[i-1].l]||i==1) flag=1;
		if(flag){
			memset(cnt,0,sizeof(cnt));
			r=R[bl[q[i].l]];mx=lst=0;
			flag=0;
		}
		while(r<q[i].r){
			r++;
			cnt[c[r]]++;
			mx=lst=max(lst,cnt[c[r]]*a[r]);//lst代表答案存档
		}
		l=R[bl[q[i].l]]+1;
		while(l>q[i].l){
			l--;
			cnt[c[l]]++;
			mx=max(mx,cnt[c[l]]*a[l]);
		}
		ans[q[i].id]=mx;
		mx=lst;//答案先更新回去
		l=R[bl[q[i].l]]+1;
		while(l>q[i].l){
			l--;
			cnt[c[l]]--;//左边部分出现次数减去
		}
	}
	for(int i=1;i<=m+del;i++) print(ans[i]);
	return 0;
}

P5906 【模板】回滚莫队&不删除莫队

考虑维护每个数最左、最右出现的位置。
在右移指针的时候，直接更新最右出现的位置，然后如果目前还没有出现过这个数，就更新最左出现的位置，否则用右减左更新答案。这样，我们就得到了右边区间的贡献。
然后保存答案，移动左指针。在移动左指针时，我们只需要更新最右端点（如果这个数在右边没有出现过），不需要更新最左端点，因为目前左指针的点一定是区间中最左的点。
当我们更新完答案之后，我们对左指针的移动进行撤销操作。由于我们只更新了最右端点，并且是只更新了右侧没有出现过的数的右端点，所以我们只需要对这类数进行撤销。具体的操作就是：
CPP
if(mx[a[l]]==l){
	mx[a[l]]=0;
}
然后在每个块结束的时候，要对目前的最左最右两个数组作清除操作。
CPP
#include<bits/stdc++.h> 
#define inf 0x3f3f3f3f
using namespace std;
int read(){
	bool f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=0;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)-48+c;
		c=getchar();
	}
	return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=2e5+10;
const int blk=460;
int L[maxn],R[maxn],bl[maxn],l,r,len;
int n,m,a[maxn],del,res,lsh[maxn];
int mn[maxn],mx[maxn],ans[maxn],clr[maxn];
struct que{
	int l,r,id;
	friend bool operator <(que x,que y){
		return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
	}
}q[maxn];
signed main(){
	n=read();
	int lxl=1;
	L[1]=1;
	while(L[lxl]+blk<n){
		R[lxl]=L[lxl]+blk-1;
		lxl++;
		L[lxl]=R[lxl-1]+1;
	}
	R[lxl]=n;
	for(int i=1;i<=lxl;i++){
		for(int j=L[i];j<=R[i];j++){
			bl[j]=i;
		}
	}
	for(int i=1;i<=n;i++){
		a[i]=lsh[i]=read();
	}
	sort(lsh+1,lsh+n+1);
	len=unique(lsh+1,lsh+n+1)-lsh-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
	}
	memset(mn,0x3f,sizeof(mn));
	m=read();
	for(int i=1;i<=m;i++){
		q[i].l=read();q[i].r=read();
		q[i].id=i+del;
		if(bl[q[i].l]==bl[q[i].r]){
            for(int j=q[i].l;j<=q[i].r;j++){
            	if(mn[a[j]]<j){
					ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
				}
                else mn[a[j]]=j;
			}
            for(int j=q[i].l;j<=q[i].r;j++){
            	mn[a[j]]=inf;
			}
            del++;i--;m--;
		}
	}
	sort(q+1,q+m+1);
	for(int k=1,i=1;k<=lxl;k++){
        l=R[k]+1,r=R[k],res=0;
        while(bl[q[i].l]==k){
            while(r<q[i].r){
                r++,mx[a[r]]=r;
                if(mn[a[r]]==inf){
                	mn[a[r]]=r;
				}
                else{
                	res=max(res,r-mn[a[r]]);
				}
            }
            ans[q[i].id]=res;
            while(l>q[i].l){
                l--;
                if(mx[a[l]]){
                	ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
				}
                else mx[a[l]]=l;
            }
            while(l<=R[k]){
            	if(mx[a[l]]==l){
            		mx[a[l]]=0;
				}
				l++;
			}
			i++;
        }
        memset(mn,0x3f,sizeof(mn));
        memset(mx,0,sizeof(mx));
	}
	for(int i=1;i<=m+del;i++){
		print(ans[i]);
	}
	return 0;
}

SP20644 ZQUERY - Zero Query

其实，这个题和上一题区别并不大。
我们先对数组做个前缀和，然后我们发现，[l,r][l,r] 区间和是 00 就等同于 l−1,rl-1,r 两个数的前缀和相等，于是方法就同上题了。
注意这里是从 sumr−suml−1=0sum_r-sum_{l-1}=0 而不是 sumr−suml=0sum_r-sum_{l}=0。
不同的是，前缀和可能会是负数，因此我们可以加一个相同的数，使其变为正数，就可以放到数组维护了。
另外，如果我们查询的区间是 [l,r][l,r]，我们需要将 l−1l-1 也考虑进来，否则我们无法表示从 ll 开始的区间。
CPP
#include<bits/stdc++.h> 
#define inf 0x3f3f3f3f
using namespace std;
int read(){
	bool f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=0;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)-48+c;
		c=getchar();
	}
	return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=52233;
const int blk=320;
int L[maxn],R[maxn],bl[maxn],st[maxn],l,r;
int n,m,a[maxn],del,top,res;
int mn[maxn<<1],mx[maxn<<1],ans[maxn],clr[maxn];
struct que{
	int l,r,id;
	friend bool operator <(que x,que y){
		return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
	}
}q[maxn];
signed main(){
	n=read();m=read();
	int lxl=1;
	L[1]=1;
	while(L[lxl]+blk<n){
		R[lxl]=L[lxl]+blk-1;
		lxl++;
		L[lxl]=R[lxl-1]+1;
	}
	R[lxl]=n;
	for(int i=1;i<=lxl;i++){
		for(int j=L[i];j<=R[i];j++){
			bl[j]=i;
		}
	}
	a[0]=maxn;
	for(int i=1;i<=n;i++){
		a[i]=read()+a[i-1];
	}
	memset(mn,0x3f,sizeof(mn));
	for(int i=1;i<=m;i++){
		q[i].l=read();q[i].r=read();
		q[i].id=i+del;
		if(bl[q[i].l]==bl[q[i].r]){
			mn[a[q[i].l-1]]=q[i].l-1;
            for(int j=q[i].l;j<=q[i].r;j++){
            	if(mn[a[j]]<j){
					ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
				}
                else mn[a[j]]=j;
			}
            mn[a[q[i].l-1]]=inf;
            for(int j=q[i].l;j<=q[i].r;j++){
            	mn[a[j]]=inf;
			}
            del++;i--;m--;
		}
		
	}
	sort(q+1,q+m+1);
	for(int k=1,i=1;k<=lxl;k++){
        l=R[k]+1,r=R[k],res=0,top=0;
        while(bl[q[i].l]==k){
            while(r<q[i].r){
                r++,mx[a[r]]=r;
                if(mn[a[r]]==inf){
                	mn[a[r]]=r,st[top++]=a[r];
				}
                else{
                	res=max(res,r-mn[a[r]]);
				}
            }
            ans[q[i].id]=res;
            while(l>=q[i].l){
                l--;
                if(mx[a[l]]){
                	ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
				}
                else mx[a[l]]=l;
            }
            while(l<=R[k]){
            	if(mx[a[l]]==l){
            		mx[a[l]]=0;
				}
				l++;
			}
			i++;
        }
        while(top--){
        	mn[st[top]]=inf,mx[st[top]]=0;
		}
	}
	for(int i=1;i<=m+del;i++){
		print(ans[i]);
	}
	return 0;
}
理论上来说，回滚莫队由于不用删除，所以可以替代所有的普通莫队。由于其思路简单，所以在实际应用的时候可能有一定的优势。
但目前的 OI 中，直接使用回滚莫队进行操作的题目并不多，大部分的题目都可以用普通莫队解决，所以这一算法的实用性不是很强。
最后，这里给出两道个人认为比较有难度的回滚莫队题，有兴趣的同学可以自行思考。

评论

共 27 条评论，欢迎与作者交流。

正在加载评论...