回滚莫队，这种莫队在不能够删除或者不能够增加的时候使用。通常用于删除和插入只有一个复杂度能够接受的情况下使用，时间复杂度也是 \(O(n\sqrt{n})\)。

下面我们以不插入莫队为例。

首先仍然是分块，如果询问左右端点都在同一个块内，那么我们直接暴力做就可以。我们也可以对整个快预处理，然后删除左右两端多余的部分。

如果左右端点不在一个块内，按照左端点所在块进行分组，每一组内右端点越大越靠前，我们右端点一直左移删除，而左端点每次到达询问后回滚，即撤销操作。撤销操作我们用栈来记录就可以。

第一类询问复杂度显然正确。第二类询问中，右端点总共移动次数为 \(O(n)\)，这是就一个块来说。对所有块来说，复杂度也是正确的。左端点的总复杂度是 \(O(q\sqrt{n})\)，其中 \(q\) 是询问次数。因为询问次数和 \(n\) 是同阶的，所以可知复杂度正确。

LOJ2874

注意到插入复杂度为 \(O(1)\)，而删除复杂度不可接受。直接用不删除莫队。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 100100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,a[N],m,Len,b[N],rk[N];
ll ans[N];
int posi[N];

struct Ques{
    int l,r,id;
}ques[N];

vector<int> q1[N],q2[N];

typedef pair<int,int> P;

struct Queue{
    int cnt[N],top;
    ll Ans;
    pair<ll,P> Stack[N];
    inline void Init(int l,int r){
        for(int i=l;i<=r;i++) cnt[a[i]]=0;
        Ans=0;
    }
    inline void Add(int k){
        Stack[++top]=make_pair(Ans,make_pair(cnt[a[k]],k));
        cnt[a[k]]++;Ans=max(Ans,1ll*cnt[a[k]]*rk[a[k]]);
    }
    inline void RollOnce(){
        int k=Stack[top].second.second;
        Ans=Stack[top].first;
        cnt[a[k]]=Stack[top].second.first;top--;
    }
    inline void RollBack(){
        while(top) RollOnce();
    }
}q;

inline void Solve1(){
    for(int i=1;i<=posi[n];i++){
        for(int j:q1[i]){
            q.Init(ques[j].l,ques[j].r);
            for(int k=ques[j].l;k<=ques[j].r;k++) q.Add(k);
            ans[ques[j].id]=q.Ans;q.RollBack();
        }
    }
}

inline bool cmp(int a,int b){
    return ques[a].r<ques[b].r;
}

inline void Solve2(){
    for(int i=1;i<=posi[n];i++){
        sort(q2[i].begin(),q2[i].end(),cmp);
        int l=i*Len+1,r=i*Len;
        q.Init((i-1)*Len+1,n);
        for(int j:q2[i]){
            int nl=l;
            while(r<ques[j].r) q.Add(++r);
            q.top=0;
            while(ques[j].l<nl) q.Add(--nl);
            ans[ques[j].id]=q.Ans;
            q.RollBack();
        }
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);read(m);for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int r=lower_bound(b+1,b+len+1,a[i])-b;
        rk[r]=a[i];a[i]=r;
    }
    Len=sqrt(n)+1;for(int i=1;i<=n;i++) posi[i]=(i-1)/Len+1;
    // printf("Len=%d\n",Len);
    for(int i=1;i<=m;i++){
        int l,r;read(l);read(r);
        ques[i].l=l;ques[i].r=r;ques[i].id=i;
        if(posi[ques[i].l]==posi[ques[i].r]) q1[posi[ques[i].l]].push_back(i);
        else q2[posi[ques[i].l]].push_back(i);
    }
    Solve1();Solve2();
    for(int i=1;i<=m;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

P5906

和上个题目一样，同理，我们用不删除莫队。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 200010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,a[N],b[N],m,ans[N],posi[N],Len;

struct Ques{
    int l,r,id;
}ques[N];
vector<int> q1[N],q2[N];

typedef pair<int,int> P;

struct Queue{
    int minn[N],maxx[N],top,Ans;
    pair<P,P> Stack[N];
    inline void Init(int l,int r){
        for(int i=l;i<=r;i++){minn[a[i]]=INF;maxx[a[i]]=-INF;}
        Ans=0;
    }
    inline void Add(int k){
        Stack[++top]=make_pair(make_pair(k,Ans),make_pair(minn[a[k]],maxx[a[k]]));
        minn[a[k]]=min(minn[a[k]],k);
        maxx[a[k]]=max(maxx[a[k]],k);
        Ans=max(Ans,maxx[a[k]]-minn[a[k]]);
    }
    inline void RollOnce(){
        int k=Stack[top].first.first;
        minn[a[k]]=Stack[top].second.first;
        maxx[a[k]]=Stack[top].second.second;
        Ans=Stack[top].first.second;top--;
    }
    inline void RollBack(){
        while(top) RollOnce();
    }
}q;

inline void Solve1(){
    for(int i=1;i<=posi[n];i++){
        // printf("i=%d size=%d\n",i,(int)q1[i].size());
        for(int j:q1[i]){
            q.Init(ques[j].l,ques[j].r);
            for(int k=ques[j].l;k<=ques[j].r;k++) q.Add(k);
            ans[ques[j].id]=q.Ans;
            q.RollBack();
        }
    }
}

inline bool cmp(int a,int b){
    return ques[a].r<ques[b].r;
}

inline void Solve2(){
    for(int i=1;i<=posi[n];i++){
        sort(q2[i].begin(),q2[i].end(),cmp);
        int l=i*Len+1,r=i*Len;
        q.Init((i-1)*Len+1,n);
        for(int j:q2[i]){
            int nl=l;
            while(r<ques[j].r) q.Add(++r);
            q.top=0;
            while(ques[j].l<nl) q.Add(--nl);
            ans[ques[j].id]=q.Ans;
            q.RollBack();
        }
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
    Len=sqrt(n)+1;
    // printf("Len=%d\n",Len);
    for(int i=1;i<=n;i++) posi[i]=(i-1)/Len+1;
    read(m);
    for(int i=1;i<=m;i++){
        read(ques[i].l);read(ques[i].r);ques[i].id=i;
        if(posi[ques[i].l]==posi[ques[i].r]) q1[posi[ques[i].l]].push_back(i);
        else q2[posi[ques[i].l]].push_back(i);
    }
    Solve1();Solve2();
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

小结

需要注意的是，有些时候插入和删除需要用数据结构来维护，比如说 WC2022 第二题就需要用链表来维护。