本文最后更新于:2020年8月24日 下午

写在前面

莫队算法用于离线解决一类区间问题。


普通莫队

如果我们已知查询为区间[l,r][l,r]的答案,并且能在O(1)O(1)的时间内通过添加或删除一个元素得到[l1,r],[l+1,r],[l,r1],[l,r+1][l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案,那么就可以考虑使用莫队算法。

做法:

  1. 首先我们对原序列分块,原序列长度NN,每块大小记为SizeSize,那么块数为N1Size+1\lfloor \frac{N-1}{Size} \rfloor +1,每块从左到右依次编号。

  2. 对所有询问[li,ri][l_i,r_i]以询问左端点所在块的序号为第一关键字,右端点的大小为第二关键字进行排序。按照这样的顺序通过添加或删除元素求解每个询问的答案。

可以证明当SizeSizeN\sqrt{N}时,总的时间复杂度为O(N1.5)O(N^{1.5})

  • 左端点在同一块时,右端点是递增的,变化NN次,共有N\sqrt{N}个块,这一部分复杂度为O(N1.5)O(N^{1.5})
  • 左端点转移到下一块时,右端点最多变化NN次,共有N\sqrt{N}个块,这一部分复杂度为O(N1.5)O(N^{1.5})
  • 左端点在同一块时,每次最多变化N\sqrt{N},转移到下一块时,最多变化2N2\sqrt{N},询问共NN个,这一部分复杂度为O(N1.5)O(N^{1.5})

模板:

const int SIZE=300;
struct Q{int l,r,order;} q[N];
bool cmp(const re &a,const re &b)
{
    if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
    return a.r<b.r;
}
int main()
{
    for(int i=1;i<=n;++i) pos[i]=(i-1)/SIZE+1;
    for(int i=1;i<=m;++i) q[i].order=i;
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0; i<=m; ++i)
    {
        int L=q[i].l ,R=q[i].r;
        while(r<R) add(++r);
        while(r>R) del(r--);
        while(l<L) del(l++);
        while(l>L) add(--l)
        ans[q[i].order]=now;
    }
    //for(int i=1; i<=m; ++i) print ans[i]
}

带修改莫队

对于一些带单点修改的问题,还是存在一种莫队姿势的。当然,一次修改要求O(1)O(1)完成。

每个修改操作记录位置和修改前后的值,这样方便还原修改。

每个询问除了记录区间[l,r][l,r]之外,还要记录在此询问之前的修改操作个数(也可以叫做时间)tt,记posxpos_x表示xx所在块的编号。

那么将所有询问按照(posl,posr,t)(pos_l,pos_r,t)做三关键字排序。那么在普通莫队的基础上,再维护一个修改时间就可以了。

可以证明当SizeSizeN23N^{\frac{2}{3}}时,左端点、右端点、以及时间的移动复杂度均为O(N53)O(N^{\frac{5}{3}}),所以总的时间复杂度为O(N53)O(N^{\frac{5}{3}})

懒得分析了。

模板:

struct Change
{
    int x,y,pre;
}c[N];

struct Ask
{
    int l,r,id,time;
}q[N];

bool cmp(const Ask &a,const Ask &b)
{
    if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
    if(pos[a.r]!=pos[b.r]) return pos[a.r]<pos[b.r];
    return a.time<b.time;
}

void change(int i,int l,int r,bool flag)
{
    int y=c[i].x;
    if(l<=y && y<=r) erase(y);
    color[y]=flag?c[i].y:c[i].pre;
    if(l<=y && y<=r) insert(y);
}

int main()
{
    size=pow(n,2.0/3)+1;
    for(int i=1;i<=n;++i) pos[i]=(i-1)/size+1;
    sort(q+1,q+numq+1,cmp);
    int l=1,r=0,curt=0;
    for(int i=1;i<=numq;++i)
    {
        while(curt<q[i].time) change(++curt,l,r,1);
        while(q[i].time<curt) change(curt--,l,r,0);
        while(l<q[i].l) erase(l++);
        while(q[i].l<l) insert(--l);
        while(q[i].r<r) erase(r--);
        while(r<q[i].r) insert(++r);
        ans[q[i].id]=now;
    }
}

回滚莫队

我们经常会遇到这样一种问题,即插入操作十分简单,但是直接删除却非常困难(举个例子,当你要维护最值时)。有没有一种办法避免删除呢?有的,用回滚莫队的姿势就好了~

回滚,rollback,其实意思应该是还原到修改之前。假设当前询问为[l,r][l,r]poslpos_l不变时,右端点一直增加,添加操作好说,和普通莫队一样做,但是左端点怎么办呢?我们可以暂时先不把开头[l,posl×Size][l,pos_l\times Size]这部分添加,然后先存个档,暴力的插入这一小段,得到当前询问的答案后,再读档还原(有些是撤销修改),这就是回滚操作了。

bzoj 4241 历史研究:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
struct ask
{
    int l,r,o;
} q[N];
int n,m;
int a[N],hs[N],pos[N],num[N];
ll now;
ll ans[N];
bool cmp(const ask &a,const ask &b)
{
    if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
    return a.r<b.r;
}
void del(int x)
{
    --num[a[x]];
}
void add(int x)
{
    ++num[a[x]];
    now=max(now,1LL*hs[a[x]]*num[a[x]]);
}
int main()
{
    scanf("%d%d",&n,&m);
    int siz=sqrt(n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        hs[i]=a[i];
        pos[i]=(i-1)/siz+1;
    }
    sort(hs+1,hs+n+1);
    int cnt=unique(hs+1,hs+n+1)-hs-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(hs+1,hs+cnt+1,a[i])-hs;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].o=i;
    }
    sort(q+1,q+m+1,cmp);
    int r=0;
    for(int i=1;i<=m;++i)
    {
        int L=q[i].l,R=q[i].r;
        if(pos[q[i].l]!=pos[q[i-1].l])
        {
            memset(num,0,sizeof(num));
            r=pos[q[i].l]*siz;
            now=0;
        }
        while(r<R) add(++r);
        ll last=now;
        for(int j=L;j<=pos[q[i].l]*siz && j<=R;++j)
            add(j);
        ans[q[i].o]=now;
        //rollback
        for(int j=L;j<=pos[q[i].l]*siz && j<=R;++j)
            del(j);
        now=last;
    }
    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

题目

普通莫队

带修改莫队

回滚莫队


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

快速傅里叶变换学习笔记 上一篇
正则表达式 下一篇