回滚莫队，又叫“不删除莫队”，在一些情况无法删除或者删除无法实现，只能增加。

回滚莫队的核心思想就是：既然只能实现一个操作，那么就只使用一个操作，剩下的交给回滚解决．

例如利用莫队解决区间最大值问题，可以区间扩大，删除困难。

回滚莫队分为只使用增加操作的回滚莫队和只使用删除操作的回滚莫队．

例1. [JOISC 2014] 历史的研究

【题意简化】给你一个长度为 $𝑛$ 的数组 $𝐴$ 和 $𝑚$ 个询问 $(1 \leq n, m \leq 10^5)$，每次询问一个区间 $[L, R]$ 内重要度最大的数字，要求 输出其重要度．一个数字 $i$ 重要度的定义为 $i$ 乘上 $i$ 在区间内出现的次数．

【分析】

1.把原数列分成 $\sqrt{n}$ 块，对询问以左端点所在块编号为第一关键字，右端点为第二关键字升序排序。这样，每一段询问的左端点在一个块内，右端点是递增的。

2.枚举每块询问，l,r 指针初始为空区间 [R+1,R]，R 是当前块右端点。

3.枚举当前块的每个询问 [ql，qr]，分两种情况处理:(1)如果当前询问的左右端点都在当前块内，暴力计算。(2)否则，把右指针 r 拓展到询问区间右端点 qr，把结果存为 last。然后，把左指针 1 拓展到询问区间左端点 ql，把结果存入答案。最后，回滚左端点 1 到原来位置 R+1，把结果滚回 last。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,q,a[N],b[N];
ll len,block[N],num;
ll mx,ans[N],c[N],cnt[N];
struct node{
    int l,r,id;
}Q[N];
bool cmp(node x,node y)
{
    if(block[x.l]==block[y.l])return x.r<y.r;
    return x.l<y.l;
}
ll cal(int l,int r)
{
    ll ret=0;
    for(int i=l;i<=r;i++)cnt[a[i]]=0;
    for(int i=l;i<=r;i++)
    {
        cnt[a[i]]++;
        ret=max(ret,b[a[i]]*cnt[a[i]]);
    }
    return ret;
}
void add(int x)
{
    c[x]++;
    mx=max(mx,(ll)c[x]*b[x]);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q;
    len=sqrt(n);  //块长
    for(int i=1;i<=n;i++)
    {
        cin>>a[i],b[i]=a[i];
        block[i]=(i-1)/len+1;  //i 的块编号
    }
    num=block[n];  //块数
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;  //离散化
    
    for(int i=1;i<=q;i++)cin>>Q[i].l>>Q[i].r,Q[i].id=i;
    sort(Q+1,Q+q+1,cmp);
    
    ll last=0;
    for(int i=1,x=1;i<=num;i++)  //第 i 块
    {
        mx=last=0;   
        for(int j=1;j<=n;j++)c[j]=0;  //清空
        int R=min(n,i*len);  //当前块右端点
        int l=R+1,r=R;  //空区间
        while(block[Q[x].l]==i)  //左端点落在了第i块
        {
            if(block[Q[x].r]==i) //暴力计算
                ans[Q[x].id]=cal(Q[x].l,Q[x].r);
            else
            {
                while(r<Q[x].r)add(a[++r]);  //向右扩展
                last=mx;   //记录
                while(l>Q[x].l)add(a[--l]);  //l向左移动
                ans[Q[x].id]=mx;
                while(l<=R)--c[a[l++]];  //回滚
                mx=last;      //回滚初值
            }
            x++;
        }
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

学习完毕

{{ select(1) }}

• YES
• NO