莫队算法(以及带修莫队)学习笔记

wfycsw · 2022-07-17 23:03:53 · 个人记录

莫队？

这个算法听起来就很高深，学完之后更是对他赞不绝口，作为离线分治中的一大经典，这个算法一点也不冷门，十分实用。以下来谈一谈本蒟蒻对它的理解。

普通莫队

先简单介绍一下，据我所知，莫队的发明者是莫涛，其运用了分块的思想，只支持离线，不支持在线（反正我不会在线莫队），多用于回答区间询问，一般的解题思路是离线排序后，移动区间两端的两个指针，更新答案。当块设S=sqrt(n),时间复杂度是O(n*sqrt(n))(不会证，记住就好)，以下是几个代码的组成部分。

inline bool cmp(const wu &x,const wu &y){return x.l/S==y.l/S?x.r<y.r:x.l<y.l;}//S为块的大小，先按左端点的坐在的块排序，块一样就按右端点排序。

inline void calc(int x,int v){//修改操作
    cnt[x]+=。。。。。。
    ans+=。。。。。。。
}

for(RI i=1;i<=m;++i){//移动指针求解答案
    l=q[i].l;r=q[i].r;
    while(L<l) calc(L++,-1);
    while(R>r) calc(R--,-1);
    while(L>l) calc(--L,1);
    while(R<r) calc(++R,1);
    ansd[q[i].id]=ans;
}

光看模板说可能很迷惑，一起来看一道经典的题。

P1494 [国家集训队] 小 Z 的袜子

题意很显然，就不解释了。 除了calc部分，其他部分套上模板就行了，所以来看calc函数：

题目要求两只颜色相同的袜子的概率，众所周知，求在n个元素里选m个的方案数就是组合，本题就是要在长度为(r-l+1)的区间里选两个袜子，所以总方案数就是C(r-l+1，2），而算概率就是求符合条件的方案数除以总方案数。然而每次只加或减去一条袜子的所改变符合条件的方案数是可以在修改前的基础上快速求出的（O(1)），不需要重新算。以下是参考代码。

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define No puts("NO"),exit(0)
#define RI register int
#define err puts("asd")
using namespace std;
inline int read(){
    RI s=0;register char c=getchar();bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
    return f?-s:s;
}
const int N=5e4+5;
struct wu{
    int l,r,id; 
}q[N];
int a[N],cnt[N],S;ll k,L=1,R,fm=1,fz=0,ans1[N],ans2[N]; 
inline bool cmp(const wu &x,const wu &y){return x.l/S==y.l/S?x.r<y.r:x.l<y.l;}
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
inline ll C(ll x){return x*(x-1)>>1;}//求C(x,2)
inline void calc(int x,int v){
    x=a[x];
    ll len=R-L+1,p,D=cnt[x];
    cnt[x]+=v;
    if(len==1){//据题目意思特判
        fm=1ll;fz=0ll;
        return;
    }
    fm=len*(len-1)>>1;fz+=C(cnt[x])-C(D);
}
signed main(){
//  freopen("1.in","r",stdin);
    RI n=read(),m=read(),l,r;S=sqrt(n);
    for(RI i=1;i<=n;++i) a[i]=read();
    for(RI i=1;i<=m;++i) q[i]=(wu){read(),read(),i};
    sort(q+1,q+m+1,cmp);
    for(RI i=1;i<=m;++i){
        l=q[i].l;r=q[i].r;
        while(L<l) calc(L++,-1);//++和--放在前还是后很好理解不多说
        while(R>r) calc(R--,-1);
        while(L>l) calc(--L,1);
        while(R<r) calc(++R,1);
        RI p=gcd(fm,fz);
//      fm/=p;fz/=p;
        ans1[q[i].id]=fz/p;ans2[q[i].id]=fm/p;
    }
    for(RI i=1;i<=m;++i)
        printf("%lld/%lld\n",ans1[i],ans2[i]);
    return 0;
}

做完模板题后，就再看几道近似的模板题吧！

P2709 小B的询问

P3709 大爷的字符串题

CF617E XOR and Favorite Number

P4396 [AHOI2013]作业

差不多了，普通莫队就完结了！

带修莫队

与普通莫队相差别的是带修莫队多了一维时间维，在这个时间维里移动，就可以回到某一次修改后的状态，因此便可以做到修改。

一般带修莫队块的大小定为n^(2/3)时时间复杂度最优，具体证明请看这

带修莫队其本质与普通莫队差不多，但代码实现当然会变得：

inline bool cmp(node x,node y){
    return x.l/S==y.l/S?(x.r/S==y.r/S?x.t<y.t:x.r<y.r):x.l<y.l;
}

inline void work(int t,int i){//多出的一个函数
    。。。。
}

for(RI i=1;i<=k;++i){//k是询问次数，带修莫队的修改操作与询问分开
    l=q[i].l;r=q[i].r;t=q[i].t;
    while(L<l) calc(L++,0);
    while(R>r) calc(R--,0);
    while(L>l) calc(--L,1);
    while(R<r) calc(++R,1);
    while(T<t) work(++T,i);
    while(T>t) work(T--,i);
    ans[q[i].id]=s;
}

来看一道经典的题:P1903 [国家集训队] 数颜色 / 维护队列

标程：

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define No puts("NO")
#define Yes puts("YES")
#define RI register int
#define err puts("asd")
using namespace std;
inline int read(){
    RI s=0;register char c=getchar();bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=getchar();
    return f?-s:s;
}
const int N=133340;
struct wu{
    int l,r,t,id;
}q[N];
int a[N],to[N],pos[N],s,ans[N],L=1,R=0,T,S,cnt[1000005],bel[N];
//inline bool cmp(const wu &x,const wu &y){return x.l/S==y.l/S?x.r<y.r:x.l<y.l;}
inline bool cmp(const wu &x,const wu &y){
    return x.l/S==y.l/S?(x.r/S==y.r/S?x.t<y.t:x.r<y.r):x.l<y.l;
}
inline void calc(int x,int v){s+=v?(++cnt[a[x]])==1:-(!--cnt[a[x]]);}
inline void work(int t,int i){
    if(q[i].l<=pos[t]&&pos[t]<=q[i].r){
        calc(pos[t],0);//删除修改前的
        swap(to[t],a[pos[t]]);//要交换，不能只赋值，下同
        calc(pos[t],1);//加入修改后的
    }
    else swap(to[t],a[pos[t]]);
}
signed main(){
    RI n=read(),m=read(),l,r,k=0,t=0;char op[10];
    S=pow(n,2.0/3.0);
//  if(S==0) err;
    for(RI i=1;i<=n;++i) bel[i]=i/S+1,a[i]=read();
    for(RI i=1;i<=m;++i){
        scanf("%s",&op);
        if(op[0]=='Q') q[++k]=(wu){read(),read(),t,k};
        else pos[++t]=read(),to[t]=read();
    }
    sort(q+1,q+k+1,cmp);
    for(RI i=1;i<=k;++i){
        l=q[i].l;r=q[i].r;t=q[i].t;
        while(L<l) calc(L++,0);
        while(R>r) calc(R--,0);
        while(L>l) calc(--L,1);
        while(R<r) calc(++R,1);
        while(T<t) work(++T,i);//注意区间的开闭
        while(T>t) work(T--,i);
        ans[q[i].id]=s;
    }
    for(RI i=1;i<=k;++i)
        printf("%d\n",ans[i]);
    return 0;
}

奇偶优化

提起奇偶优化，自我感觉是他很玄学，其实用性的证明请看这。

其实不太理解也没关系，毕竟不是强制要求的，只是加了会快一点，所以记住模板就行了：

普通莫队：

inline bool cmp(node &x,node &y){return bel[x.l]^bel[y.l]?x.l<y.l:(bel[x.l]&1?x.r<y.r:x.r>y.r);}

带修莫队:

inline bool cmp(node &x,node &y){
    return bel[x.l]^bel[y.l]?x.l<y.l:(bel[x.r]^bel[y.r]?(bel[x.l]&1?x.r<y.r:x.r>y.r):x.t<y.t)
}

当然，莫队的种类不止这两种，我会在将来进行更深入的学习。