浅谈回滚莫队

BFqwq

2020-10-29 20:25:18

Algo. & Theory

回滚莫队

前置知识：莫队。

不会的同学可以看往期日报

回滚莫队，听起来好像很高级的样子。

但其实，它还有个很平凡的名字——不删除莫队。

回顾普通的莫队，其实说到底一共只有四个操作，分别是 l++,l--,r++,r--。

而这些操作实际上又分成两大类，分别是插入和删除。

简单的说，当我们执行完 l-- 或是 r++ 的操作后，我们的区间变长了，相当于我们向区间内插入了一个数。

而另外两个操作之后呢，我们的区间变短了，相当于我们从区间中删除了一个数。

虽然在平时的莫队中，这两者的复杂度是一样的，但显然，删除的操作往往更为复杂，甚至有的时候我们能很简单的完成插入操作，但却一直想不到如何进行删除。这个时候，我们的回滚莫队就要登场了。

我们先通过一个比较简单的例子来了解一下回滚莫队。

区间众数问题

给定一个序列以及若干次询问，求区间众数，可离线。

这个问题是个经典的问题，目前有许多的解法。但从思维难度上来讲，回滚莫队可能是最简单的。

考虑莫队。我们维护一个 f 数组代表出现次数，当我们要插入一个数时，我们只需要更新这个数的次数，然后和最大值作比较。这是大家都能想到的。

但要删除一个数就显得比较复杂，于是我们可以对莫队作一点变化。

首先，对于左右端点位于一个块内的询问，我们直接暴力，这样的复杂度显然正确。

接着，我们依然按照左端点排序，将左端点在同一个块内的数拿出来一起处理。

我们直接将右指针移到该左端点所在块的右端点处，然后暴力向右插入。这样，在块外的部分的贡献我们就可以统计了。

然后我们将状态保存，然后将左指针移到左端点所在块的右端点 +1 处，向左插入，将块内的部分的贡献加入。

然后，我们再将左端点逐个移回，并撤销左区间的贡献即可。注意这里是撤销，而不是删除。

具体的实现方法很多，比如我们在右端点时将区间众数答案保存（定义一个变量 lst=ans），然后左端点插入时修改 f 数组，撤回时依然修改 f 数组，然后将答案变回（ans=lst）。

这样，我们的 f 数组和 ans 最终都没有发生变化，而左指针又回到了左端点所在块的右端点 +1，就好像什么也没有发生。

右端点的复杂度之和显然是 \operatorname O(n\sqrt n)，和莫队相同。而左端点由于每次的移动不超过 \sqrt n，顾复杂度为 \operatorname O(m\sqrt n)。因此，莫队的复杂度没有发生任何变化。

以上就是回滚莫队的基本内容，通过巧妙的变换莫队的指针位置来避免了删除操作。

当然实际上我们也可以类似的弄一个不插入莫队（这个名字是自己取的qaq），但由于一般很少见到插入比删除麻烦的题，所以实际作用不大。

下面我们来做几道题练练手。

AT1219 歴史の研究

https://www.luogu.com.cn/problem/AT1219

实际上，这个题和区间众数的区别不是很大，只不过是在更新答案的时候再乘以一个 X_i。

和区间众数一样，我们维护一个数的出现次数。然后跑回滚莫队。更新答案时用事件的发生次数乘以重要度，与目前答案取最大值作为答案。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
char cr[200];int tt;
inline void print(int x,char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=1e6+10;
const int blk=405;
int n,a[maxn],m,bl[maxn],cnt[maxn];
int L[maxn],R[maxn],ans[maxn],mx,lst;
int lsh[maxn],len,c[maxn],del;
bool flag=0;
struct query{
    int l,r,id;
    friend bool operator <(query c,query d){
        if(bl[c.l]==bl[d.l]) return c.r<d.r;
        return c.l<d.l;
    }
}q[maxn];
int chk(int l,int r){
    mx=0;
    for(int i=l;i<=r;i++){
        cnt[c[i]]++;
        mx=max(a[i]*cnt[c[i]],mx);
    }
    for(int i=l;i<=r;i++) cnt[c[i]]--;
    return mx;
}
signed main(){
    n=read();m=read();
    int lxl=1;
    L[1]=1;
    while(L[lxl]+blk<n){
        R[lxl]=L[lxl]+blk-1;
        lxl++;
        L[lxl]=R[lxl-1]+1;
    }
    R[lxl]=n;
    for(int i=1;i<=lxl;i++){
        for(int j=L[i];j<=R[i];j++){
            bl[j]=i;
        }
    }
    for(int i=1;i<=n;i++){
        a[i]=lsh[i]=c[i]=read();
    }
    sort(lsh+1,lsh+n+1);
    len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++)
        c[i]=lower_bound(lsh+1,lsh+len+1,c[i])-lsh;
    for(int i=1;i<=m;i++){
        q[i].l=read();q[i].r=read();q[i].id=i+del;
        if(bl[q[i].l]==bl[q[i].r]){
            ans[i+del]=chk(q[i].l,q[i].r);
            i--,m--,del++;
        }
    }
    sort(q+1,q+m+1);
    int l,r;
    for(int i=1;i<=m;i++){
        if(bl[q[i].l]!=bl[q[i-1].l]||i==1) flag=1;
        if(flag){
            memset(cnt,0,sizeof(cnt));
            r=R[bl[q[i].l]];mx=lst=0;
            flag=0;
        }
        while(r<q[i].r){
            r++;
            cnt[c[r]]++;
            mx=lst=max(lst,cnt[c[r]]*a[r]);//lst代表答案存档
        }
        l=R[bl[q[i].l]]+1;
        while(l>q[i].l){
            l--;
            cnt[c[l]]++;
            mx=max(mx,cnt[c[l]]*a[l]);
        }
        ans[q[i].id]=mx;
        mx=lst;//答案先更新回去
        l=R[bl[q[i].l]]+1;
        while(l>q[i].l){
            l--;
            cnt[c[l]]--;//左边部分出现次数减去
        }
    }
    for(int i=1;i<=m+del;i++) print(ans[i]);
    return 0;
}

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

考虑维护每个数最左、最右出现的位置。

在右移指针的时候，直接更新最右出现的位置，然后如果目前还没有出现过这个数，就更新最左出现的位置，否则用右减左更新答案。这样，我们就得到了右边区间的贡献。

然后保存答案，移动左指针。在移动左指针时，我们只需要更新最右端点（如果这个数在右边没有出现过），不需要更新最左端点，因为目前左指针的点一定是区间中最左的点。

当我们更新完答案之后，我们对左指针的移动进行撤销操作。由于我们只更新了最右端点，并且是只更新了右侧没有出现过的数的右端点，所以我们只需要对这类数进行撤销。具体的操作就是：

if(mx[a[l]]==l){
    mx[a[l]]=0;
}

然后在每个块结束的时候，要对目前的最左最右两个数组作清除操作。

#include<bits/stdc++.h> 
#define inf 0x3f3f3f3f
using namespace std;
int read(){
    bool f=1;
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=0;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)-48+c;
        c=getchar();
    }
    return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=2e5+10;
const int blk=460;
int L[maxn],R[maxn],bl[maxn],l,r,len;
int n,m,a[maxn],del,res,lsh[maxn];
int mn[maxn],mx[maxn],ans[maxn],clr[maxn];
struct que{
    int l,r,id;
    friend bool operator <(que x,que y){
        return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
    }
}q[maxn];
signed main(){
    n=read();
    int lxl=1;
    L[1]=1;
    while(L[lxl]+blk<n){
        R[lxl]=L[lxl]+blk-1;
        lxl++;
        L[lxl]=R[lxl-1]+1;
    }
    R[lxl]=n;
    for(int i=1;i<=lxl;i++){
        for(int j=L[i];j<=R[i];j++){
            bl[j]=i;
        }
    }
    for(int i=1;i<=n;i++){
        a[i]=lsh[i]=read();
    }
    sort(lsh+1,lsh+n+1);
    len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
    }
    memset(mn,0x3f,sizeof(mn));
    m=read();
    for(int i=1;i<=m;i++){
        q[i].l=read();q[i].r=read();
        q[i].id=i+del;
        if(bl[q[i].l]==bl[q[i].r]){
            for(int j=q[i].l;j<=q[i].r;j++){
                if(mn[a[j]]<j){
                    ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
                }
                else mn[a[j]]=j;
            }
            for(int j=q[i].l;j<=q[i].r;j++){
                mn[a[j]]=inf;
            }
            del++;i--;m--;
        }
    }
    sort(q+1,q+m+1);
    for(int k=1,i=1;k<=lxl;k++){
        l=R[k]+1,r=R[k],res=0;
        while(bl[q[i].l]==k){
            while(r<q[i].r){
                r++,mx[a[r]]=r;
                if(mn[a[r]]==inf){
                    mn[a[r]]=r;
                }
                else{
                    res=max(res,r-mn[a[r]]);
                }
            }
            ans[q[i].id]=res;
            while(l>q[i].l){
                l--;
                if(mx[a[l]]){
                    ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
                }
                else mx[a[l]]=l;
            }
            while(l<=R[k]){
                if(mx[a[l]]==l){
                    mx[a[l]]=0;
                }
                l++;
            }
            i++;
        }
        memset(mn,0x3f,sizeof(mn));
        memset(mx,0,sizeof(mx));
    }
    for(int i=1;i<=m+del;i++){
        print(ans[i]);
    }
    return 0;
}

SP20644 ZQUERY - Zero Query

其实，这个题和上一题区别并不大。

我们先对数组做个前缀和，然后我们发现，[l,r] 区间和是 0 就等同于 l-1,r 两个数的前缀和相等，于是方法就同上题了。

注意这里是从 sum_r-sum_{l-1}=0 而不是 sum_r-sum_{l}=0。

不同的是，前缀和可能会是负数，因此我们可以加一个相同的数，使其变为正数，就可以放到数组维护了。

另外，如果我们查询的区间是 [l,r]，我们需要将 l-1 也考虑进来，否则我们无法表示从 l 开始的区间。

#include<bits/stdc++.h> 
#define inf 0x3f3f3f3f
using namespace std;
int read(){
    bool f=1;
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=0;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)-48+c;
        c=getchar();
    }
    return f?x:x*-1;
}
char cr[200];int tt;
inline void print(register int x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=52233;
const int blk=320;
int L[maxn],R[maxn],bl[maxn],st[maxn],l,r;
int n,m,a[maxn],del,top,res;
int mn[maxn<<1],mx[maxn<<1],ans[maxn],clr[maxn];
struct que{
    int l,r,id;
    friend bool operator <(que x,que y){
        return bl[x.l]^bl[y.l]?x.l<y.l:x.r<y.r;
    }
}q[maxn];
signed main(){
    n=read();m=read();
    int lxl=1;
    L[1]=1;
    while(L[lxl]+blk<n){
        R[lxl]=L[lxl]+blk-1;
        lxl++;
        L[lxl]=R[lxl-1]+1;
    }
    R[lxl]=n;
    for(int i=1;i<=lxl;i++){
        for(int j=L[i];j<=R[i];j++){
            bl[j]=i;
        }
    }
    a[0]=maxn;
    for(int i=1;i<=n;i++){
        a[i]=read()+a[i-1];
    }
    memset(mn,0x3f,sizeof(mn));
    for(int i=1;i<=m;i++){
        q[i].l=read();q[i].r=read();
        q[i].id=i+del;
        if(bl[q[i].l]==bl[q[i].r]){
            mn[a[q[i].l-1]]=q[i].l-1;
            for(int j=q[i].l;j<=q[i].r;j++){
                if(mn[a[j]]<j){
                    ans[q[i].id]=max(ans[q[i].id],j-mn[a[j]]);
                }
                else mn[a[j]]=j;
            }
            mn[a[q[i].l-1]]=inf;
            for(int j=q[i].l;j<=q[i].r;j++){
                mn[a[j]]=inf;
            }
            del++;i--;m--;
        }

    }
    sort(q+1,q+m+1);
    for(int k=1,i=1;k<=lxl;k++){
        l=R[k]+1,r=R[k],res=0,top=0;
        while(bl[q[i].l]==k){
            while(r<q[i].r){
                r++,mx[a[r]]=r;
                if(mn[a[r]]==inf){
                    mn[a[r]]=r,st[top++]=a[r];
                }
                else{
                    res=max(res,r-mn[a[r]]);
                }
            }
            ans[q[i].id]=res;
            while(l>=q[i].l){
                l--;
                if(mx[a[l]]){
                    ans[q[i].id]=max(ans[q[i].id],mx[a[l]]-l);
                }
                else mx[a[l]]=l;
            }
            while(l<=R[k]){
                if(mx[a[l]]==l){
                    mx[a[l]]=0;
                }
                l++;
            }
            i++;
        }
        while(top--){
            mn[st[top]]=inf,mx[st[top]]=0;
        }
    }
    for(int i=1;i<=m+del;i++){
        print(ans[i]);
    }
    return 0;
}

理论上来说，回滚莫队由于不用删除，所以可以替代所有的普通莫队。由于其思路简单，所以在实际应用的时候可能有一定的优势。

但目前的 OI 中，直接使用回滚莫队进行操作的题目并不多，大部分的题目都可以用普通莫队解决，所以这一算法的实用性不是很强。

最后，这里给出两道个人认为比较有难度的回滚莫队题，有兴趣的同学可以自行思考。

P6072 『MdOI R1』Path
P6580 [Ynoi2019]美好的每一天~不连续的存在