学习

莫队算法

Wider · 1月27日 · 2020年 · · 2550次已读

莫队算法

传说中能解决一切区间问题的算法

这个算法是由之前的国家队队长莫涛巨神(%%%)发明的,所以尊称莫队算法。

  • 目前的题型概括为三种:普通莫队,树形莫队以及带修莫队。这里讲普通莫队算法

  • 题目
    P2709 小B的询问

  • 题目描述

    小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求\sum{C_i^2}的值,其中i的值从1到K,其中C_i表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

分析&举个栗子

掌握一个思想基础:两个询问之间的状态跳转。如图,当前完成的询问的区间为[a,b],下一个询问的区间为[p,q],现在保存[a,b]区间内的每个颜色出现次数的cnt[]数组已经准备好,[a,b]区间询问的答案ans1已经准备好,怎样用这些条件求出[p,q]区间询问的ans2
enter image description here

考虑指针向左或向右移动一个单位,我们要付出多大的代价才能维护ans?即使得ans保存的是当前[l,r]的信息。我们对图中l,r的向右移动一格进行分析:
enter image description here

如图l指针向右移动一个单位,所造成的后果就是:我们损失了一个绿色方块。那么怎样维护:cnt[绿色]-1。那ans如何维护?
(C_i+1)^2=C_i^2+(2\times C_i+1) \\
(C_i-1)^2=C_i^2-(2\times C_i-1)

不难看出,我们可以直接向给以前ans +2*c[i]+1(或 -(2*c[i]-1))。同理,下面的r指针移动,将是差不多的。

enter image description here

如图r指针的移动带来的后果是,我们多了一个橙色方块。所以操作和上文相似,只不过是cnt[橙色]++

回归正题地,我们发现,知道一个区间的信息,要求出旁边区间的信息(旁边区间指的是当前区间的一个指针通过加一减一得到的区间),竟只需要O(1)的时间。

但是就算是这样,到这里为止的话莫队算法依旧无法焕发其光彩,原因是:如果我们以读入的顺序来枚举每个询问,每个询问到下一个询问时都用上述方法维护信息,那么在你脑海中会浮现出l,r跳来跳去的疯狂景象,疯狂之处在于最坏情况下时间复杂度为:O(n^2)——如果要这样玩,那不如写一个暴力程序。

“莫队算法巧妙地将询问离线排序,使得其复杂度无比美妙……”

在一般做题时我们时常遇到使用排序来优化枚举时间消耗的例子。莫队的优化基于分块思想:对于两个询问,若在其l在同块,那么将其r作为排序关键字,若l不在同块,就将l作为关键字排序(这就是双关键字)。若使用pos[i]数组表示i所属的块是谁。排序如:

bool operator <(const Mo &rhs) const
{
    if(pos==rhs.pos)return r<rhs.r;
    else return l<rhs.l;
}

值得强调的是,我们是在对询问进行操作。

时间复杂度分析(分类讨论思想):

首先,枚举m个答案,就一个m了。设分块大小为unit

分类讨论:

1. l的移动:若下一个询问与当前询问的l所在的块不同,那么只需要经过最多2*unit步可以使得l成功到达目标.复杂度为:O(m*unit)

2. r的移动:r只有在pos[l]相同时才会有序(其余时候还是疯狂地乱跳,你知道,一提到乱跳,那么每一次最坏就要跳n次!),pos[l]什么时候相同?在同一块里面lpos[]相同。对于每一个块,排序执行了第二关键字:r。所以这里面的r是单调递增的,所以枚举完一个块,r最多移动n次。总共有n/unit个块:复杂度为:O(n*n/unit)

总结O(n*unit+n^2/unit)(n,m同级,就统一使用n)

根据基本不等式得:当n为 sqrt(n) 时,得到莫队算法的最优复杂度O(n\sqrt n)

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 50010
#define LL long long
using namespace std;
int n,m,k,unit;
struct Mo
{
    int l;
    int r;
    int id;
    int pos;
    bool operator <(const Mo &rhs) const
    {
        if(pos==rhs.pos)return r<rhs.r;
        else return l<rhs.l;
    }
}a[N];
int b[N],cnt[N];
LL Ans[N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    unit=sqrt(n+1);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].id=i;
        a[i].pos=a[i].l/unit;
    }
    sort(a+1,a+1+m);
    int l=1,r=0;
    LL ans=0;
    for(int i=1;i<=m;i++)
    {
        while(l>a[i].l){l--;ans+=(cnt[b[l]]*2+1);cnt[b[l]]++;}
        while(r<a[i].r){r++;ans+=(cnt[b[r]]*2+1);cnt[b[r]]++;}
        while(l<a[i].l){ans-=(cnt[b[l]]*2-1);cnt[b[l]]--;l++;}
        while(r>a[i].r){ans-=(cnt[b[r]]*2-1);cnt[b[r]]--;r--;}
        Ans[a[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
    printf("%lld\n",Ans[i]);
    return 0;
}

注: 部分引自大米饼的博客

树上莫队

树上莫队是莫队算法的拓展,思想依然差不多,下面我介绍一种树上莫队的做法。

首先弄出树的括号序。(对树做一次深搜,第一次进入某节点时,将此节点编号加入序列,从某节点退出时,将此节点编号第二次加入序列)
如图,有一棵树,以及它的括号序:

然后记录一个数在括号序中第一次出现和最后一次出现的位置。
如果要询问j到k之间路径的信息,需进行分类讨论:
(以下均遵循此原则,出现两次的数字不算入所求信息中)
1.如果j是k的祖先,那么所求信息就为j和k最后出现的位置之间的信息。
2.如果j不是k的祖先。那么所求信息就为j最先出现的位置以及k最后出现的位置之间的信息,我们发现,j,k的lca不在其中,再把lca加上即可。

那么实现的时候就是用change来表示一个点的出现情况的改变。

然后当做序列上的莫队来做就可以了。
注: 引自DoBelieve的博客

带修改莫队

题目

墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令:
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求,你知道你需要干什么了吗?

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define N 10005
using namespace std;
int qid=0,tim=0,cx[1000005],res,block[N],ans[N],a[N];
struct ask{int l,r,t,id;}q[N];
struct chan{int x,y;}ch[1005];
int cmp(ask a,ask b){
    if (block[a.l]==block[b.l])
    {
        if (a.r==b.r) return a.t<b.t;
        else return a.r<b.r;
    }else return a.l<b.l;
}
void change(int now,int i)
{
    if (ch[now].x>=q[i].l && ch[now].x<=q[i].r) 
    {
        cx[a[ch[now].x]]--;
        if (cx[a[ch[now].x]]==0) res--;
        if (cx[ch[now].y]==0) res++;
        cx[ch[now].y]++;            
    }
    swap(a[ch[now].x],ch[now].y);
}
int main()
{
    int n,m,i;
    scanf("%d%d",&n,&m);
    int size=sqrt(n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]),block[i]=(i-1)/size+1;
    for (i=1;i<=m;i++)
    {
        int l,r;char s[5];
        scanf("%s%d%d",s,&l,&r);
        if (s[0]=='Q'){
            q[++qid].l=l; q[qid].r=r; q[qid].id=qid; q[qid].t=tim;
        }
        else ch[++tim].x=l,ch[tim].y=r;
    }
    sort(q+1,q+qid+1,cmp);
    int l=0,r=0,now=0;
    for (i=1;i<=qid;i++)
    {
        while (l<q[i].l){cx[a[l]]--;if (cx[a[l]]==0) res--; l++;}
        while (l>q[i].l){l--;if (cx[a[l]]==0) res++; cx[a[l]]++;}
        while (r<q[i].r){r++;if (cx[a[r]]==0) res++; cx[a[r]]++;}
        while (r>q[i].r){cx[a[r]]--;if (cx[a[r]]==0) res--; r--;}
        while (now<q[i].t){now++;change(now,i);}
        while (now>q[i].t){change(now,i);now--;}
        ans[q[i].id]=res;
    }
    for (i=1;i<=qid;i++)  printf("%d\n",ans[i]);
}

我们继续分块。
把二元组L,R变成三元组L,R,x。x是这次询问在修改第几次后。

然后把R所在块看作第二关键字,x看作第三关键字排序即可。

转移时直接恢复(或删除)两次询问之间的修改。如果在区间内还要计算对答案的影响

然而修改的复杂度不同

最优分块方式是每块 N^{2 \over 3},总共 N^{1\over 3}

左指针移动 N*N^{2 \over 3}=N^{5 \over 3}

右指针移动 N*N^{2 \over 3}=N^{5 \over 3}

修改指针移动(N^{1 \over 3})^2*N=N^{5 \over 3}

总复杂度 N^{5 \over 3}
在实际操作中,有时取一些什么 \sqrt n*10 之类的奇葩的数可能更快

注: 引自BAJim_H的博客

0 条回应