什么是回滚莫队啊（战术后仰）

首先确定一个常数$len$(一般而言取 $\sqrt{n}$ ,$n^{\frac{2}{3}}$)，将数组分为$\lceil {\frac{n}{len}} \rceil$个块 对于$m$个区间询问，将其按照左端点$l$所属的块从小到大排序，然后对于左端点在同一个块内的数据吗，将右端点$r$按从小到大排序

然后枚举每个块，让我们来处理所有左端点在这个块内的询问

我们知道一个性质，左端点在同一个块内的询问，右端点从左到右排序，所以右端点是单调的，我们用一个不会回退的指针$rr$来统计右边的结果

现在来考虑左端点，虽然左端点是无序的，但是由于它们都在同一个块内，所以它们离这个块的右端点的距离都不会超过$len$，所以我们用一个可以回退的指针 $ll$ 来统计左边的答案

由于同一个块内的询问的右端点是递增的，因此 $rr$ 产生的贡献在统计这个块内询问时是永久的，不用删除，而左端点是无序的，产生的贡献需要删除。

$ll$ 和 $rr$ 都从这个区间的右端点出发，首先$rr$从上一个询问的右端点走向这一个询问的右端点，然后$ll$从块的右端点出发，向左走统计左边的贡献
，注意 $ll$ 统计的贡献是临时的，因此统计完之后要让$ll$从此询问的左端点回归到块的右端点，同时删除贡献。

以下是需要注意的几点

1. 需要有一个不会归零的量记录$rr$统计到的贡献
2. 左右端点在同一个块内的询问可以直接暴力，反正也就O（$len$）的复杂度

来考虑复杂度，对于一个区块内的询问，指针 $rr$ 最多从这个区块右端点移动的序列右端点，最多移动 $n$ 次，最多有$\lceil {\frac{n}{len}} \rceil$个区间，所以复杂度最多为O（$nlen$）。

对于单个询问，指针 $ll$ 在这个块内移动，每个询问最多移动$len$ 次，对于所有的 $m$ 个询问，最多移动O（$mlen$）次。

因为 $m$ ， $n$同级，可以证明算法的复杂度为O（$nlen$）,大多数情况复杂度为O（$n\sqrt n$）

回滚莫队有一个好处，即只需要增操作，不需要减操作，对与某些无法实现减操作（比如查询最大值）的题目尤其好用

例题：P3380【模板】回滚莫队&不删除莫队

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,m,a[N],las[N],tmp[N],qlen,qn,bel[N],mr[N],ans[N],st[N],ed[N],num[N],cnt;
struct node{
	int l,r,id;
}qt[200010];
bool cmp(node a1,node a2) {return (bel[a1.l]==bel[a2.l])?(a1.r<a2.r):(bel[a1.l]<bel[a2.l]);}
int calc(int l,int r) {
	int res=0;
	for(int i=l; i<=r; i++) las[a[i]]=0;
	for(int i=l; i<=r; i++) (las[a[i]]==0)?(las[a[i]]=i):(res=max(res,i-las[a[i]]));
	return res;
}
int main()
{
	cin>>n;
	qlen=sqrt(n);
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		tmp[i]=a[i],bel[i]=(i-1)/qlen+1;
		mr[bel[i]]=i;
	}
	qn=bel[n],mr[bel[n]]=n;
	sort(tmp+1,tmp+n+1);
	int tn=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1; i<=n; i++) a[i]=lower_bound(tmp+1,tmp+tn+1,a[i])-tmp;
    cin>>m;
    for(int i=1; i<=m; i++) {
    	cin>>qt[i].l>>qt[i].r;
    	qt[i].id=i;
	}
    sort(qt+1,qt+m+1,cmp);
    int now=1;
    for(int i=1; i<=qn; i++) {
    	int l=mr[i]+1,r=l-1,mx=0;
    	cnt=0;
    	while(bel[qt[now].l]==i) {
    		if(bel[qt[now].r]==i) {
    			ans[qt[now].id]=calc(qt[now].l,qt[now].r),now++;
    			continue;
			} 
			while(r<qt[now].r) {
				r++;
				ed[a[r]]=r;
				if(!st[a[r]]) st[a[r]]=r,num[++cnt]=a[r];
				mx=max(mx,r-st[a[r]]);
			}
			int t1=mx;
			while(l>qt[now].l) {
				l--;
				if(!ed[a[l]]) ed[a[l]]=l;
				else mx=max(mx,ed[a[l]]-l);
			}
			ans[qt[now].id]=mx;
			while(l<=mr[i]) {
				if(ed[a[l]]==l) ed[a[l]]=0;
				l++;
			} 
			mx=t1;
    		now++;
		}
		for(int j=1; j<=cnt; j++) st[num[j]]=ed[num[j]]=0;
	}
	for(int i=1; i<=m; i++) cout<<ans[i]<<endl;
	return 0;
}

AT1219歴史の研究

#include<bits/stdc++.h>
#define N 500010
using namespace std;
long long n,q,a[N],bel[N],qlen,mr[N],ans[N],bac[N],num[N],cnt,bac2[N],tmp[N],dui[N];
struct node{
	long long l,r,id;
}pt[100010];
bool cmp(node a1,node a2) {
	return (bel[a1.l]==bel[a2.l])?(a1.r<a2.r):(bel[a1.l]<bel[a2.l]);
}
long long calc(long long l,long long r) {
	long long res=0;
	for(long long i=l; i<=r; i++) bac2[a[i]]=0;
	for(long long i=l; i<=r; i++) bac2[a[i]]+=dui[a[i]],res=max(res,bac2[a[i]]);
	return res;
}
int main()
{
	cin>>n>>q;
	qlen=sqrt(n);
	for(long long i=1; i<=n; i++) {
		cin>>a[i];tmp[i]=a[i];
		bel[i]=(i-1)/qlen+1,mr[bel[i]]=i;
	}
	sort(tmp+1,tmp+n+1);
	int tn=unique(tmp+1,tmp+n+1)-tmp-1;
	for(int i=1; i<=n; i++) {
		int tp=a[i];
		a[i]=lower_bound(tmp+1,tmp+tn+1,a[i])-tmp;
		dui[a[i]]=tp;
	}
	for(long long i=1; i<=q; i++) {
		cin>>pt[i].l>>pt[i].r;
		pt[i].id=i;
	}
	sort(pt+1,pt+q+1,cmp);
	long long now=1;
	for(long long i=1; i<=bel[n]; i++) {
		long long l=mr[i]+1,r=l-1,mx=0;
		cnt=0;
		while(bel[pt[now].l]==i) {
			if(bel[pt[now].r]==i) {
				ans[pt[now].id]=calc(pt[now].l,pt[now].r);
				now++;continue;
			}
			while(r<pt[now].r) r++,bac[a[r]]+=dui[a[r]],mx=max(mx,bac[a[r]]),num[++cnt]=a[r];
			long long tp=mx;
			while(l>pt[now].l) l--,bac[a[l]]+=dui[a[l]],mx=max(mx,bac[a[l]]);
			ans[pt[now].id]=mx;
			while(l<=mr[i]) bac[a[l]]-=dui[a[l]],l++;
			now++,mx=tp;
		}
		for(long long j=1; j<=cnt; j++) bac[num[j]]=0;
	}
	for(long long i=1; i<=q; i++) cout<<ans[i]<<endl;
	return 0;
}

upd2022/1/20:只删回滚莫队

与前面提到的只加回滚莫队相反，只删回滚莫队通过将询问左端点按块递增排序，将左端点在同一个块内的询问按右端点降序排序，$l$ 指针复位时回到块的最左端而不是最右端， $r$ 指针从右往左扫来实现只有删除操作的效果。

例题：P8078 [WC2022] 秃子酋长

这种莫队的例题比较稀少，目前也只找到一道。