回滚莫队

介绍

在一些用莫队处理的问题中，扩展区间容易但收缩区间不好处理，这时可以考虑使用回滚莫队的技巧，以达到区间只增不减的效果。

具体步骤

1. 对询问离线并排序，以左端点所在块号为第一关键字，右端点大小为第二关键字进行排序

2. 以块号递增的顺序处理询问，每次只考虑左端点在该块内的询问

3. 暴力回答所有左右端点都在块内的询问

4. 记当前块号为 $k$，区间为 $[st[k],ed[k]]$，考虑剩下的询问，显然询问的右端点都大于 $ed[k]$ 并且递增

5. 记当前已求得答案的区间为 $[l,r]$，答案为 $pre$，若该询问是该块内的第一次询问则初始化区间为 $[l=ed[k]+1, r=ed[k]]$

6. 扩展 $r$ 至当前询问的右边界，并更新答案 $pre$

7. 建立临时变量 $ans=pre$，扩展 $l$ 至当前询问的左边界，并更新答案 $ans$，扩展完毕后用 $ans$ 回答当前询问

8. 回撤左端点 $l$ 至 $ed[k]+1$，并撤销扩展 $l$ 时对辅助变量的更改，保留 $pre$ 用于下次询问（即回撤区间至 $[ed[k],r]$）

这样我们就实现了区间只增不减的莫队，步骤 8 中撤销左边界的具体实现视所用辅助变量而定，例如桶的话就 $cnt[value]—$，并查集的话用按秩合以支持撤销操作。

分析下复杂度，假定 $n$ 和 $m$ 同数量级，取块大小 $B = \sqrt{n}$，暴力处理块内询问 $O(\sqrt{n})$，每个块内右端点至多扩展 $n$ 次 $O(n\sqrt{n})$，左端点每次最多扩展和撤销 $\sqrt{n}$ 次，因此总复杂度仍为 $O(n\sqrt{n})$。

模板

AtCoder1219 历史研究

扩展右端点：cnt[x]++,pre=max(pre,cnt[x]*x)

扩展右端点：cnt[x]++,ans=max(ans,cnt[x]*x)

回撤左端点：cnt[x]--

const int SZ = sqrt(MAXN);
vector<int> X;
int n,m,z;
int a[MAXN],b[MAXN],cnt[MAXN],id[MAXN],st[MAXN],ed[MAXN],t[MAXN];
struct query
{
    int l,r,i; LL ans;
    bool operator <(const query &t)const
    {
        if(id[t.l]!=id[l])return id[l]<id[t.l];
        return r<t.r;
    }
}q[MAXN];
inline LL baoli(int l,int r)
{
    LL ans=0;
    fp(i,l,r)t[b[i]]++,ans=max(ans,1LL*t[b[i]]*a[i]);
    fp(i,l,r)t[b[i]]--;
    return ans;
}
int work()
{
    scanf("%d%d",&n,&m);
    fp(i,1,n)scanf("%d",&a[i]),X.pb(a[i]);
    fp(i,1,n)id[i]=(i-1)/SZ+1; z=id[n];
    fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
    fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
    sort(all(X)),unq(X);
    fp(i,1,n)b[i]=lb(all(X),a[i])-X.begin()+1;
    fp(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i;
    sort(q+1,q+1+m);
    LL ans=0,pre=0;
    for(int i=1,l,r;i<=m;i++)
    {   
        int k=id[q[i].l];
        if(id[q[i].l]!=id[q[i-1].l])mst(cnt,0),ans=pre=0,r=ed[k],l=ed[k]+1;
        if(id[q[i].l]==id[q[i].r])q[i].ans=baoli(q[i].l,q[i].r);
        else
        {
            while(l<=ed[k])cnt[b[l]]--,l++;
            while(r<q[i].r)r++,cnt[b[r]]++,pre=max(pre,1LL*cnt[b[r]]*a[r]);
            ans=pre;
            while(l>q[i].l)l--,cnt[b[l]]++,ans=max(ans,1LL*cnt[b[l]]*a[l]);
            q[i].ans=ans;
        }
    }
    sort(q+1,q+1+m,[](const query &a,const query &b){return a.i<b.i;});
    fp(i,1,m)printf("%lld\n",q[i].ans);
    return 0;
}

练习

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

扩展右端点再更新答案的同时记录每个数的最右出现位置，扩展左端点时用区间内最靠右的位置更新答案。

const int SZ = sqrt(MAXN);

int n,m;
int a[MAXN],t[MAXN],s1[MAXN],s2[MAXN];
int id[MAXN],st[MAXN],ed[MAXN];
struct query{int l,r,i,ans;}q[MAXN];
vector<int> X;
int baoli(int l,int r)
{
    int ans=0;
    fp(i,l,r)
        if(!t[a[i]]) t[a[i]]=i;
        else ans=max(ans,i-t[a[i]]);
    fp(i,l,r)t[a[i]]=0;
    return ans;
}
int work()
{
    scanf("%d",&n);
    fp(i,1,n)scanf("%d",&a[i]),X.pb(a[i]);
    fp(i,1,n)id[i]=(i-1)/SZ+1;
    fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
    fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
    sort(all(X)),unq(X);
    fp(i,1,n)a[i]=lb(all(X),a[i])-X.begin()+1;
    scanf("%d",&m);
    fp(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].i=i;
    sort(q+1,q+1+m,[](const query &a,const query &b)
    {
        if(id[a.l]!=id[b.l])return id[a.l]<id[b.l];
        return a.r<b.r;
    });
    int pre=0,ans=0,l,r;
    fp(i,1,m)
    {
        int k=id[q[i].l];
        if(id[q[i].l]!=id[q[i-1].l])
        {
            r=ed[k],l=ed[k]+1,ans=pre=0,mst(s1,0),mst(s2,0);
        }
        if(id[q[i].l]==id[q[i].r])q[i].ans=baoli(q[i].l,q[i].r);
        else
        {
            while(r<q[i].r)
            {
                r++,s2[a[r]]=r;
                if(!s1[a[r]])s1[a[r]]=r;
                else pre=max(pre,r-s1[a[r]]);
            }
            ans=pre;
            while(l>q[i].l)
            {
                l--;
                if(!t[a[l]])t[a[l]]=l;
                else ans=max(ans,t[a[l]]-l);
                if(s2[a[l]])ans=max(ans,s2[a[l]]-l);
            }
            while(l<=ed[k])t[a[l]]=0,l++;
            q[i].ans=ans;
        }
    }
    sort(q+1,q+1+m,[](const query &a,const query &b){return a.i<b.i;});
    fp(i,1,m)printf("%d\n",q[i].ans);
    return 0;
}

ICPC2017北京C

显然扩展区间时用并查集可以很简单的维护答案，实现并查集撤销后应用回滚莫队即可

这题有点玄学，理论上来说应该按度数分块，因为扩展区间的复杂度并不是 $O(1)$ 的，而是取决于该点向区间内的连边数。那么应该保证块内总度数在 $\sqrt{m}$ 的数量级内。。。但这么分块会 TLE，估计数据的连边都是随机的，每个块内的边数都在 $\sqrt{n}$ 左右吧。

const int B = sqrt(50000);
struct dsu
{
    struct info{int fa,sz;}t[MAXN];
    vector<pair<int,info>> v;
    void init(int n)
    {
        fp(i,1,n)t[i]={i,1};
        v.clear();
    }
    int find(int x){return t[x].fa==x?x:find(t[x].fa);}
    LL merge(int a,int b)
    {
        int fa=find(a),fb=find(b); LL ans=0;
        v.pb({fa,t[fa]});
        v.pb({fb,t[fb]});
        if(fa!=fb)
        {
            if(t[fa].sz>t[fb].sz)swap(fa,fb);
            ans=1LL*t[fa].sz*t[fb].sz;
            t[fa].fa=fb;
            t[fb].sz+=t[fa].sz;
        }
        return ans;
    }
    void undo()
    {
        t[v.back().fi]=v.back().se,v.ppb();
        t[v.back().fi]=v.back().se,v.ppb();
    }
}S,T;

int n,m,q;
int id[MAXN],st[MAXN],ed[MAXN];
vector<int> G[MAXN];
struct edge{int u,v;}e[MAXN];
struct query{int l,r;LL ans;int i;}a[MAXN];
void add(int i,int l,int r,dsu &d,LL &ans,int &cnt)
{
    auto it = lb(all(G[i]),l), ed = ub(all(G[i]),r);
    for(;it!=ed;it++)
    {
        int j=*it;
        ans+=d.merge(i,j);
        cnt++;
    }
}
LL baoli(int l,int r)
{
    int cnt=0; LL ans=0;
    fp(i,l,r)add(i,l,r,T,ans,cnt);
    while(cnt--)T.undo();
    return ans;
}
int work()
{
    MC
    {
        scanf("%d%d%d",&n,&m,&q);
        S.init(n),T.init(n);
        fp(i,1,n)G[i].clear();
        fp(i,1,n)id[i]=(i-1)/B+1,st[id[i]]=ed[id[i]]=0;
        fp(i,1,n)if(!st[id[i]])st[id[i]]=i;
        fd(i,n,1)if(!ed[id[i]])ed[id[i]]=i;
        fp(i,1,m)scanf("%d%d",&e[i].u,&e[i].v);
        fp(i,1,q)scanf("%d%d",&a[i].l,&a[i].r),a[i].i=i;
        sort(a+1,a+1+q,[](const query &a,const query &b)
        {
            if(id[a.l]!=id[b.l])return id[a.l]<id[b.l];
            return a.r<b.r;
        });
        fp(i,1,m)G[e[i].u].pb(e[i].v),G[e[i].v].pb(e[i].u);
        fp(i,1,n)sort(all(G[i]));
        int l,r; LL ans=0,pre=0;
        fp(i,1,q)
        {
            int k=id[a[i].l];
            if(id[a[i].l]!=id[a[i-1].l])S.init(n),ans=pre=0,r=ed[k],l=ed[k]+1;
            if(id[a[i].l]==id[a[i].r])a[i].ans=baoli(a[i].l,a[i].r);
            else
            {   
                int cnt=0;
                while(r<a[i].r)r++,add(r,l,r,S,pre,cnt);
                cnt=0,ans=pre;
                while(l>a[i].l)l--,add(l,l,r,S,ans,cnt);
                a[i].ans=ans,l=ed[k]+1;
                while(cnt--)S.undo();
            }
        }
        fp(i,1,n)G[i].clear();
        sort(a+1,a+1+q,[](const query &a,const query &b)
        {
            return a.i<b.i;
        });
        fp(i,1,q)printf("%lld\n",a[i].ans);
    }
    return 0;
}