很多时候，在进行莫队操作时，会遇到添加容易删除难的问题。 比如涉及到最值的运算。 这时，可以使用回滚莫队。
首先，和普通莫队一样，对序列进行分块。 对于左右端点在同一个块的询问，直接暴力求解。
然后，枚举左端点所在的块，并将右端点排序。 将左端点设为区间右端点，右端点从小到大移动。
这样，左端点每次移动不超过\(O(\sqrt n)\)，移动后将左端点再恢复回区间右端点的位置。 时间复杂度：\(O(m \sqrt n)\)。
例题：
AT1219 歴史の研究代码：
#include <stdio.h> #include <stdlib.h> #include <vector> #include <math.h> #define ll long long using namespace std; struct SPx { int z,i; }; SPx px[100010]; int cmp1(const void*a,const void*b) { return ((SPx*)a)->z-((SPx*)b)->z; } int sz[100010],ls[100010],sl[100010];ll ma,ans[100010]; void add(int x) { sl[x]+=1; ll t=1ll*ls[x]*sl[x]; if(t>ma)ma=t; } ll baoli(int l,int r) { ma=0; for(int i=l;i<=r;i++) add(sz[i]); ll rt=ma;ma=0; for(int i=l;i<=r;i++) sl[sz[i]]-=1; return rt; } struct SJd { int i,l,r; }; SJd jd[100010]; vector<SJd> ve[500]; int cmp2(const void*a,const void*b) { return ((SJd*)a)->r-((SJd*)b)->r; } int ku[100010],st[500],en[500]; int main() { int n,m=0,q; scanf("%d%d",&n,&q); for(int i=0;i<n;i++) { scanf("%d",&px[i].z); px[i].i=i+1; } qsort(px,n,sizeof(SPx),cmp1); for(int i=0;i<n;i++) { if(i==0||px[i].z>px[i-1].z) m+=1; sz[px[i].i]=m;ls[m]=px[i].z; } int B=int(sqrt(n)+0.5),k=0; while(1) { st[k+1]=en[k]+1;k+=1; en[k]=st[k]+B-1; if(en[k]>=n) { en[k]=n; break; } } for(int i=1;i<=k;i++) { for(int j=st[i];j<=en[i];j++) ku[j]=i; } for(int i=0;i<q;i++) { SJd t;t.i=i; scanf("%d%d",&t.l,&t.r); if(ku[t.l]==ku[t.r]) ans[i]=baoli(t.l,t.r); else ve[ku[t.l]].push_back(t); } for(int i=1;i<=k;i++) { int z=ve[i].size(); for(int j=0;j<z;j++) jd[j]=ve[i][j]; qsort(jd,z,sizeof(SJd),cmp2); int l=en[i],r=l-1;ma=0; for(int j=1;j<=m;j++) sl[j]=0; for(int j=0;j<z;j++) { while(r<jd[j].r) { r+=1; add(sz[r]); } ll od=ma; while(l>jd[j].l) { l-=1; add(sz[l]); } ans[jd[j].i]=ma;ma=od; while(l<en[i]) { sl[sz[l]]-=1; l+=1; } } } for(int i=0;i<q;i++) printf("%lld\n",ans[i]); return 0; }