莫队学习笔记

lizhous · 2023-03-08 17:35:05 · 个人记录

概念

莫队是一种幽雅的暴力。用于处理区间问题。

核心思想就是把询问离线下来，然后维护双指针按一定顺序处理每个询问。精髓就在于一定顺序。

首先确定一个块长，然后将左端点的位置除以块长，把询问分成若干块。在每个块里按右端点排序。发现当块长为 \sqrt n 时两个指针各移动 n\sqrt n 次，然后做即可。

模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int n,m,a[100001];
int ans[100001];
int sq;
struct item
{
    int l,r,md,i;
}fucl[1000001];
bool cmp(item a,item b)
{
    if(a.md==b.md) return a.r<b.r;
    return a.md<b.md;
}
void add(int w)
{
    //some
}
void del(int w)
{
    //some
}
signed main()
{
    freopen("god.in","r",stdin);
    freopen("god.out","w",stdout);
//  freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.in","r",stdin);
//  freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    sq=500;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&fucl[i].l,&fucl[i].r);
        fucl[i].md=fucl[i].l/sq;
        fucl[i].i=i;
    }
    sort(fucl+1,fucl+m+1,cmp);
    int l,r=0;
    l=1;
    for(int i=1;i<=m;i++)
    {
        while(r<fucl[i].r)
        {
            r++;
            add(a[r]);
        }
        while(r>fucl[i].r)
        {
            del(a[r]);
            r--;
        }
        while(l<fucl[i].l)
        {
            del(a[l]);
            l++;
        }
        while(l>fucl[i].l)
        {
            l--;
            add(a[l]);
        }
        ans[fucl[i].i]=/*some*/;
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans[i]);
    }
}

回滚莫队

回滚莫队可以面对删点麻烦的情况，核心操作是撤销操作。

与普通莫队一样，我们对询问离线并按值域分块。假如我们在处理的块是左端点在 [l,r] 中的。我们最开始把右端点放到 r 并初始化所有东西。因为右端点有序，所以直接扫过去。每次处理询问时先处理好右端点，然后左端点从 r 开始前移到目标位置，此时就获得了答案。再把左端点移动产生的贡献撤销。时间复杂度是 n\sqrt n。需要注意的是撤销的时间复杂度问题。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,m,len,answ[200001],a[200001],lsh[200001],sq,fi[200001],la[200001],fii[200001],laa[200001],ans;
struct qw
{
    int l,r,md,i;
}q[200001];
bool vis[200001];
int use[200001],lenn;
bool cmp(qw a,qw b)
{
    if(a.md==b.md) return a.r<b.r;
    return a.md<b.md;
}
void add(int w,int i)
{
    la[w]=max(la[w],i);
    fi[w]=min(fi[w],i);
    ans=max(ans,la[w]-fi[w]);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        lsh[i]=a[i];
    }
    sort(lsh+1,lsh+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(lsh+1,lsh+n+1,a[i])-lsh;
    }
    scanf("%lld",&m);
    sq=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].md=q[i].l/sq;
        q[i].i=i;
    }
    sort(q+1,q+m+1,cmp);
    int l,r;
    q[0].md=-1;
    for(int z=1;z<=n;z++)
    {
        la[z]=-100000000;
        fi[z]=100000000;
    }
    r=(q[1].md+1)*sq;
    r--;
    for(int i=1;i<=m;i++)
    {
        if(q[i].md!=q[i-1].md)
        {
            r=(q[i].md+1)*sq;
            r--;
            for(int z=1;z<=n;z++)
            {
                la[z]=-100000000;
                fi[z]=100000000;
            }
            ans=0;
        }
        if(q[i].r<=(q[i].md+1)*sq) continue;
        while(r<q[i].r)
        {
            r++;
            add(a[r],r);
        }
        l=(q[i].md+1)*sq;
        int anss=ans;
        while(l>q[i].l)
        {
            l--;
            if(!vis[a[l]])
            {
                laa[a[l]]=la[a[l]];
                use[++lenn]=a[l];
                fii[a[l]]=fi[a[l]];
                vis[a[l]]=true;
            }
            laa[a[l]]=max(laa[a[l]],l);
            fii[a[l]]=min(fii[a[l]],l);
            anss=max(anss,laa[a[l]]-fii[a[l]]);
        }
        for(int z=1;z<=lenn;z++)
        {
            vis[use[z]]=false;
        }
        lenn=0;
        answ[q[i].i]=anss;
    }
    for(int i=1;i<=m;i++)
    {
        if(q[i].r<=(q[i].md+1)*sq)
        {
            int anss=0;
            for(int z=q[i].l;z<=q[i].r;z++)
            {
                if(!vis[a[z]])
                {
                    laa[a[z]]=-100000000;
                    use[++lenn]=a[z];
                    fii[a[z]]=100000000;
                    vis[a[z]]=true;
                }
                laa[a[z]]=max(laa[a[z]],z);
                fii[a[z]]=min(fii[a[z]],z);
                anss=max(anss,laa[a[z]]-fii[a[z]]);
            }
            answ[q[i].i]=anss;
            for(int z=1;z<=lenn;z++)
            {
                vis[use[z]]=false;
            }
            lenn=0;
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",answ[i]);
    }
}

带修莫队

带有修改的莫队问题。

把修改抽象为时间轴，即每时刻进行一次修改，一个时刻内有很多询问。

相当于莫队多了一维。传统的，对前两维 (l,r) 分块，块内按时间排序。

之后就和普通莫队差不多了，多滚一维时间轴，注意滚的时候可能对答案有影响，需要更新答案。

需要记录撤销修改的结果。

块长 ^{1.5}\sqrt{n}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int n,m,a[200001],ton[1000001],beb[200001],len,lne,cnt;
int ans[200001];
int sq;
struct item
{
    int l,r,tim,md,i;
}fucl[200001],chg[200001];
bool cmp(item a,item b)
{
    if(a.md==b.md)
    {
        if(a.r/sq==b.r/sq)
        {
            return a.tim<b.tim;
        }
        return a.r<b.r;
    }
    return a.md<b.md;
}
void add(int w)
{
    ton[w]++;
    if(ton[w]==1) cnt++;
}
void del(int w)
{
    ton[w]--;
    if(ton[w]==0) cnt--;
}
void chsg(int w,int l,int r)
{
    if(chg[w].l>=l&&chg[w].l<=r)
    {
        del(a[chg[w].l]);
    }
    a[chg[w].l]=chg[w].r;
    if(chg[w].l>=l&&chg[w].l<=r)
    {
        add(a[chg[w].l]);
    }
}
void ghc(int w,int l,int r)
{
    if(chg[w].l>=l&&chg[w].l<=r)
    {
        del(a[chg[w].l]);
    }
    a[chg[w].l]=chg[w].md;
    if(chg[w].l>=l&&chg[w].l<=r)
    {
        add(a[chg[w].l]);
    }
}
signed main()
{
//  freopen("dp.in","r",stdin);
//  freopen("dp.out","w",stdout);
//  freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.in","r",stdin);
//  freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    sq=ceil(exp((log(n)+log(n))/3));
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        beb[i]=a[i];
    }
    for(int i=1;i<=m;i++)
    {
        char op;
        scanf(" %c",&op);
        if(op=='Q')
        {
            len++;
            scanf("%lld%lld",&fucl[len].l,&fucl[len].r);
            fucl[len].md=fucl[len].l/sq;
            fucl[len].i=len;
            fucl[len].tim=lne;
        }
        else
        {
            lne++;
            scanf("%lld%lld",&chg[lne].l,&chg[lne].r);
//          chg[lne].md=chg[lne].l/sq;
            chg[lne].md=beb[chg[lne].l];
            beb[chg[lne].l]=chg[lne].r;
            chg[lne].i=i;
        }
    }
    sort(fucl+1,fucl+len+1,cmp);
    int l,r=0,tim=0;
    l=1;
    for(int i=1;i<=len;i++)
    {
        while(r<fucl[i].r)
        {
            r++;
            add(a[r]);
        }
        while(r>fucl[i].r)
        {
            del(a[r]);
            r--;
        }
        while(l<fucl[i].l)
        {
            del(a[l]);
            l++;
        }
        while(l>fucl[i].l)
        {
            l--;
            add(a[l]);
        }
        while(tim<fucl[i].tim)
        {
            tim++;
            chsg(tim,l,r);
        }
        while(tim>fucl[i].tim)
        {
            ghc(tim,l,r);
            tim--;
        }
        ans[fucl[i].i]=cnt;
    }
    for(int i=1;i<=len;i++)
    {
        printf("%lld\n",ans[i]);
    }
}