莫队算法总结

本文章最后修改于2018年5月7日。


写在前面

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


普通莫队

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

做法:

1.首先我们对原序列分块,原序列长度,每块大小记为,那么块数为,每块从左到右依次编号。

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

可以证明当取时,总的时间复杂度为。

  • 左端点在同一块时,右端点是递增的,变化次,共有个块,这一部分复杂度为。
  • 左端点转移到下一块时,右端点最多变化次,共有个块,这一部分复杂度为。
  • 左端点在同一块时,每次最多变化,转移到下一块时,最多变化,询问共个,这一部分复杂度为。

模板:

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]
}

带修改莫队

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

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

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

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

可以证明当取时,左端点、右端点、以及时间的移动复杂度均为,所以总的时间复杂度为。

懒得分析了。

模板:

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

题目

普通莫队

带修改莫队

回滚莫队

 

不定期更新~