莫队算法小结

没学之前以为莫队算法是一个十分高深的算法，学了才发现其实这个算法挺简单的，除去证明部分(划掉)也挺快上手的。

https://www.cnblogs.com/Paul-Guderian/p/6933799.html

题目：https://blog.csdn.net/qq_41289920/article/details/82715231

树上莫队：https://www.cnblogs.com/zwfymqz/p/9223425.html#_label1_0

莫队是一种“优雅的暴力”，号称能解决所有的区间问题的算法。简单分类为：无修改的莫队，带修改的莫队和树上莫队。

无修改的莫队/普通莫队

原理以及证明上面博客的大佬已经说得很清楚了，蒟蒻就不献丑了，其实是我不会证明。总而言之，莫队算法的精髓和核心就在于对询问按照左右端点进行特别的排序，询问排序后的单点修改总次数能达到一个比较优秀的时间复杂度是O(Nsqrt(N))（这是单点操作时间复杂度为O(1)的情况）。

以BZOJ1878 HH的项链 作为例题

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=2e5+10,B=233;
#define bel(x) ((x-1)/B+1)
int n,m,a[N],sum,ans[M],c[1000010];
struct query{
    int id,l,r;
    bool operator < (const query &rhs) const {
        return bel(l)==bel(rhs.l) ? r<rhs.r : l<rhs.l;  //询问排序顺序 
    }
}q[M];

void add(int x) {  //添加操作 
    if (!c[x]) sum++;
    c[x]++;
}

void del(int x) {  //删除操作 
    c[x]--;
    if (!c[x]) sum--;
}

void solve() {  //莫队算法 
    int pl=1,pr=0;
    for (int i=1;i<=m;i++) {
        while (pl<q[i].l) del(a[pl++]);
        while (pl>q[i].l) add(a[--pl]);
        while (pr<q[i].r) add(a[++pr]);
        while (pr>q[i].r) del(a[pr--]);
        ans[q[i].id]=sum;
    }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    cin>>m;
    for (int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    
    sort(q+1,q+m+1);  //把询问排序 
    solve();
    for (int i=1;i<=m;i++) printf("%d
",ans[i]);
    return 0;
}

View Code

带修改的莫队

我们发现上面哪一题数组的值是不会改变的，如果像 BZOJ2120 数颜色 这一题这样数组的值会改变该怎么办？这就得用到带修改得莫队。

因为增加了修改操作，那么每一次的询问前面的修改操作都必须完成才能正确地处理询问。那么我们给询问加多一个纬度tim(之前只有l，r)，tim代表该次询问之前有多少次修改操作。与此同时再莫队算法的时候也应该增加一个时间纬度Tim代表此时的莫队处理了前Tim个修改操作且当前区间在[pl,pr]。

也就是说我们可以把修改该操作当成时间，对于某个询问q[i]，此时莫队处理到的Tim必须等于q[i].tim才能处理这个询问（当然也不能忽略前两个纬度l=pl,r=pr）。如若Tim!=q[i].tim怎么办？多了就往回退修改操作，少了就增加修改操作呗，莫队真不愧是优雅的暴力。。。

这样的时间复杂度为 $O (n^{\frac{5}{3}})$

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,B=233;
#define bel(x) ((x-1)/B+1)
int n,m,pl=1,pr=0,num,Tim,sum,a[N],ans[N],c[1000010];
struct query{
    int tim,l,r,id;
    bool operator < (const query &rhs) const {
        if (bel(l)!=bel(rhs.l)) return l<rhs.l;
        if (bel(r)!=bel(rhs.r)) return r<rhs.r;
        return tim<rhs.tim;
    }
}q[N];
struct change{ int x,New,Old; }p[N];

void update(int x,int v) {  //v=1是增加  v=-1是删除 
    if (c[x]==0) sum++;
    c[x]+=v;
    if (c[x]==0) sum--;
}

void recall(int x,int v) {  //对修改操作的时间回溯 
    if (pl<=x && x<=pr) update(a[x],-1),update(v,1);
    a[x]=v;
}

void solve() {
    for (int i=1;i<=num;i++) {
        while (Tim<q[i].tim) Tim++,recall(p[Tim].x,p[Tim].New);
        while (Tim>q[i].tim) recall(p[Tim].x,p[Tim].Old),Tim--;
        
        while (pl<q[i].l) update(a[pl++],-1);
        while (pl>q[i].l) update(a[--pl],1);
        while (pr<q[i].r) update(a[++pr],1);
        while (pr>q[i].r) update(a[pr--],-1);
        ans[q[i].id]=sum;
    }
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    num=0,Tim=0;  //num个询问  Tim个修改 
    for (int i=1;i<=m;i++) {
        char s[3]; int l,r; scanf("%s%d%d",s,&l,&r);
        if (s[0]=='Q') q[++num]=(query){Tim,l,r,num};
        if (s[0]=='R') p[++Tim]=(change){l,r,a[l]},a[l]=r; 
    }
    
    sort(q+1,q+num+1);
    solve();
    for (int i=1;i<=num;i++) printf("%d
",ans[i]);
    return 0;
}

View Code

树上莫队

莫队在树上的做法要比在数组麻烦得多。主要问题有几个：①树怎么分块 ②块怎么排序 ③树怎么分左右起点终点，起终点怎么移动？

看了网上的资料似乎有两种比较常用的树上莫队：一种是用dfs按结点个数大小把树上分块，然后再在树上做路径的端点移动实现莫队。另一种是用欧拉序把树转变成区间，那么查询的路径也变成了区间，然后就可以转化为普通的线性莫队来做了。

我学的是欧拉序的树上莫队,方法及原理上面大佬已经说得很好了。

这里以SPOJ-COT2为例给出模板代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10,M=1e5+10;
#define bel(x) ((x-1)/B+1)
int B,n,m,sum,v[N],b[N],st[N],ed[N],er[N<<1],p[M],c[M],ans[M];
vector<int> G[N];
struct query{
    int id,l,r,lca;
    bool operator < (const query &rhs) const {
        return bel(l)==bel(rhs.l) ? r<rhs.r : bel(l)<bel(rhs.l);
    }
}q[M];

/*-------------------------树链剖分求LCA-----------------------------*/
struct node{
    int dep,fa,sz,heavy;
    int top; 
}tree[N]; 

int num=0;
void dfs1(int x,int fa,int dep) {  
    tree[x].dep=dep;
    tree[x].fa=fa;
    tree[x].sz=1;
    
    st[x]=++num; er[num]=x;  //欧拉序 
    int maxson=-1;
    for (int i=0;i<G[x].size();i++) {
        int y=G[x][i];
        if (y==fa) continue;
        dfs1(y,x,dep+1);
        tree[x].sz+=tree[y].sz;
        if (tree[y].sz>maxson) tree[x].heavy=y,maxson=tree[y].sz;
    }
    ed[x]=++num; er[num]=x; //欧拉序 
}

void dfs2(int x,int top) {  //点x所在树链的top 
    tree[x].top=top;
    if (!tree[x].heavy) return;  //叶子结点 
    dfs2(tree[x].heavy,top);  //先剖分重儿子 
    for (int i=0;i<G[x].size();i++) {  //再剖分轻儿子 
        int y=G[x][i];
        if (y==tree[x].fa || y==tree[x].heavy) continue;
        dfs2(y,y);
    }
}

int LCA(int x,int y) {
    while (tree[x].top!=tree[y].top) {
        if (tree[tree[x].top].dep<tree[tree[y].top].dep) swap(x,y);
        x=tree[tree[x].top].fa;
    }
    if (tree[x].dep>tree[y].dep) swap(x,y);
    return x;
}

/*-------------------------莫队算法-----------------------------*/
void change(int x,int val) {
    if (c[x]==0) sum++;
    c[x]+=val;
    if (c[x]==0) sum--;
}

void update(int x) {
    if (p[x]) change(v[x],-1); else change(v[x],1);
    p[x]^=1;
}

void solve() {
    int pl=1,pr=0;
    for (int i=1;i<=m;i++) {
        while (pl<q[i].l) update(er[pl++]);
        while (pl>q[i].l) update(er[--pl]);
        while (pr<q[i].r) update(er[++pr]);
        while (pr>q[i].r) update(er[pr--]);
        if (q[i].lca) update(q[i].lca);  //因为欧拉序路径不经过LCA需要特判 
        ans[q[i].id]=sum;
        if (q[i].lca) update(q[i].lca);  //欧拉序不经过路径一旦特判完就立即删除 
    }
}

void Discrete() {  //离散化 
    int tot=n;
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-(b+1);
    for (int i=1;i<=n;i++) v[i]=lower_bound(b+1,b+tot+1,v[i])-b;
}

int main()
{
    cin>>n>>m;
    B=sqrt(n);  //分块大小 
    for (int i=1;i<=n;i++) scanf("%d",&v[i]),b[i]=v[i];
    Discrete();
    for (int i=1;i<n;i++) {
        int x,y; scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for (int i=1;i<=m;i++) {
        int x,y; scanf("%d%d",&x,&y);
        if (st[x]>st[y]) swap(x,y);
        int lca=LCA(x,y);
        if (lca==x) q[i]=(query){i,st[x],st[y],0};  //LCA为x时候区间为[st[x],st[y]] 
        else q[i]=(query){i,ed[x],st[y],lca};  //LCA不是xy是区间为[ed[x],st[y]] 
    }
    sort(q+1,q+m+1);
    solve();
    for (int i=1;i<=m;i++) printf("%d
",ans[i]);
    return 0;
}

View Code

二维莫队

这个还没学，留个坑（逃）

最后借用上面大佬博客的莫队使用限制。

题目练习：