莫队算法总结

写在前面

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

普通莫队

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

做法：

首先我们对原序列分块，原序列长度 $N$ ,每块大小记为 $Size$ ，那么块数为 $\lfloor \frac{N-1}{Size} \rfloor +1$ ，每块从左到右依次编号。
对所有询问 $[l_i,r_i]$ 以询问左端点所在块的序号为第一关键字，右端点的大小为第二关键字进行排序。按照这样的顺序通过添加或删除元素求解每个询问的答案。

可以证明当 $Size$ 取 $\sqrt{N}$ 时，总的时间复杂度为 $O(N^{1.5})$ 。

左端点在同一块时，右端点是递增的，变化 $N$ 次，共有 $\sqrt{N}$ 个块，这一部分复杂度为 $O(N^{1.5})$ 。
左端点转移到下一块时，右端点最多变化 $N$ 次，共有 $\sqrt{N}$ 个块，这一部分复杂度为 $O(N^{1.5})$ 。
左端点在同一块时，每次最多变化 $\sqrt{N}$ ，转移到下一块时，最多变化 $2\sqrt{N}$ ，询问共 $N$ 个，这一部分复杂度为 $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)$ 完成。

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

每个询问除了记录区间 $[l,r]$ 之外，还要记录在此询问之前的修改操作个数（也可以叫做时间） $t$ ，记 $pos_x$ 表示 $x$ 所在块的编号。

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

可以证明当 $Size$ 取 $N^{\frac{2}{3}}$ 时，左端点、右端点、以及时间的移动复杂度均为 $O(N^{\frac{5}{3}})$ ，所以总的时间复杂度为 $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]$ 。 $pos_l$ 不变时，右端点一直增加，添加操作好说，和普通莫队一样做，但是左端点怎么办呢？我们可以暂时先不把开头 $[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;
}