莫队算法初探

log 2022.9.27 复活更新回滚莫队，删除了关于HH的项链的因为时代变迁的过时说法

普通莫队

莫队算法（mo's algorithm）一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然也有树上莫队，带修改莫队、二维莫队等等。这篇文章主要介绍的是普通莫队算法

我们考虑一个问题，给一个序列，m次询问，每次询问你区间[l,r]有多少种不同的颜色。n,m\leq 100000

尽管可以用主席树做，但是我们假装不行

先考虑暴力，对每次询问遍历一遍[l,r]，这样是O(nm)的，

换种方式暴力，定义ql和qr，表示区间[ql,qr]内有多少颜色，再定义cnt数组，cnt_i表示第i种颜色在区间[ql,qr]出现了多少次。

我们一个一个询问处理，对于询问[l,r]，我们挪动xl到l，xr到r

因为这个是莫队算法的基础，所以模拟一下这个过程：

我们的初始在这个状态，假设蓝色为1，红色为2，绿色为3

那么cnt_1=3,cnt_2=3,cnt_3=1，我们把qr向右挪一下

这样多了一个绿色，cnt_3加1

继续挪一下

多了一个红色，cnt_2加上1

此时我们发现，我们的右指针已经和询问的右端点重合了，接下来挪左指针

少了一个蓝色，cnt_1减去1

现在我们得出了答案为3，cnt_1=2,cnt_2=4,cnt_3=2

提供这部分的代码：

inline void add(int x){
    cnt[x]++;
    if(cnt[x]==1)ans++;
}

inline void del(int x){
    cnt[x]--;
    if(cnt[x]==0)ans--;
}

//在获取答案时：
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);

我们发现，每次挪动都都是O(1)的，每次询问我们最多要挪动n次，所以时间复杂度还是O(nm)。

我们有没有办法来加速呢？

这种暴力的耗时就耗在挪动次数上，我们要让他挪动的次数尽量少

肯定是有的，我们将询问先储存下来，再按照某种方法排序，让他减少挪动的次数，这样会变快一些

这种方法是强行离线,然后排序，所以这样的普通莫队不能资瓷修改

那么怎么排序呢？

一种解决方式是优先按照左端点排序。

这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最后面，从最后面挪到最前面，这样的复杂度还是O(nm)，是不行的

我们的排序是要使左右端点挪动的次数尽量少，所以这里就有一种排序方法：

将序列分成\sqrt{n}个长度为\sqrt{n}的块，若左端点在同一个块内，则按右端点排序（以左端点所在块为第一关键字，右端点为第二关键字）

注意，莫队的挪动操作要尽量快，若不是O(1)的，复杂度会原地爆炸

对于n与m同阶，一般可以设块长度为\sqrt{n}.

以下内容可以忽略，是我口胡的证明

可以证明，这样的复杂度是O(n\sqrt{n})的，简略的提一下证明过程

我们排序之后，每个块内均摊有根号\sqrt{n}个询问的l端点，显然这l个端点的右端点是有序的，最多一共会移动n次，所以对于一个块，复杂度是O(n)

然后有根号n个块，所以总的复杂度是O(n\sqrt{n})

但对于询问特别大的情况，O(n\sqrt{n})可能会超时，需要用其他的长度，我们来分析一下什么情况下均摊复杂度最优

我们设块长度为S，那么对于任意多个在同一块内的询问，挪动的距离就是n，一共\frac{n}{S}个块，移动的总次数就是\frac{n^2}{S}，移动可能跨越块，所以还要加上一个mS的复杂度，总复杂度为O(\frac{n^2}{S}+mS)，我们要让这个值尽量小，S取\frac{n}{\sqrt{m}}是最优的，此时复杂度为O(\frac{n^2}{\frac{n}{\sqrt{m}}}+m(\frac{n}{\sqrt{m}}))=O(n\sqrt{m})

然而在随机情况下，发现块大小是\frac{n}{\sqrt{m\times\frac{2}{3}}}反而会快一些（因为询问的区间大小期望是 n\times \frac{2}{3}，因此每次挪动距离当成 \frac{2}{3}n 处理）

还有一种卡常方法，按照奇偶性排序，我们正常的排序方式是这样的：

bool cmp(query a,query b){
return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

奇偶性排序是这样的：

bool cmp(node a,node b){
return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r;
}

这样能快是因为指针移到右边后不用再跳回左边，而跳回左边后处理下一个块又要跳回右边，这样能减少一半操作，理论上能快一倍

注意：分块时块的大小不是固定的，要根据题目具体分析，分析的过程如上面分析m极大时的复杂度

刚刚那道数颜色其实是 [SDOI2009]HH的项链，然而现在裸的莫队过不去了。

然而莫队吸口氧卡卡常还是能过的，不开O2会TLE 2

然而现在过不了力，有没有卡常大师再优化一手

#include <bits/stdc++.h>

using namespace std;

int read()
{
    char x;
    while((x = getchar()) > '9' || x < '0') ;
    int u = x - '0';
    while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
    return u;
}
int buf[105];  
inline void write(int i) {  
    int p = 0;  
    if(i == 0) p++;  
    else while(i) {  
        buf[p++] = i % 10;  
        i /= 10;  
    }  
    for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);  
} 

#define il inline
#define re register

int block,ans=0,cnt[1000001];
int n,m,a[500010],Ans[500010];

struct node {
    int l,r,id;
}q[500010];

il bool cmp(node a,node b){
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

il void add(int x){
    if(!cnt[a[x]])ans++;
    cnt[a[x]]++;
}

il void del(int x){
    cnt[a[x]]--;
    if(!cnt[a[x]])ans--;
}
int i;

int main(){
    n=read();
    for(i=1;i<=n;++i)a[i]=read();
    m=read();
    block=n/sqrt(m*2/3);
    for(i=1;i<=m;++i){
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=0,r=0;
    for(i=1;i<=m;++i){
        int ql=q[i].l,qr=q[i].r;
        while(l<ql)del(l++);
        while(l>ql)add(--l);
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        Ans[q[i].id]=ans;
    }
    for(i=1;i<=m;++i)write(Ans[i]),printf("\n");
    return 0;
}

接下来是：P2709 小B的询问

经典题，是裸的莫队

一句话题意：求一个区间中每个数出现次数的平方和

还是设cnt_i为i在当前区间出现的次数

如果cnt_i多了一个，那

ans+=2*cnt[x]+1

如果cnt_i多了一个，那

ans-=2*cnt[x]-1

没了。

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=50005;
long long int c[maxn];
long long int sum[maxn];

struct node{
    long long int l,r,num;
}q[maxn];

long long anss[maxn];

long long int block;
long long int ans=0;

bool cmp(node a,node b){
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}

inline void del(int x){
    sum[c[x]]--;
    ans-=2*sum[c[x]]+1;
}

inline void add(int x){
    sum[c[x]]++;
    ans+=2*sum[c[x]]-1;
}

int main()
{
    long long int n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    block=sqrt(n);
    for(long long int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
    }
    for(long long int i=1;i<=m;i++){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].num=i;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(long long int i=1;i<=m;i++){
        long long int ql=q[i].l,qr=q[i].r;
        while(l<ql){
            del(l);
            l++;
        }
        while(l>ql){
            l--;
            add(l);
        }
        while(r<qr){
            r++;
            add(r);
        }
        while(r>qr){
            del(r);
            r--;
        }
        anss[q[i].num]=ans;
    }
    for(long long int i=1;i<=m;i++){
        printf("%lld\n",anss[i]);
    }
    return 0;
}

带修改莫队

普通莫队是不能带修改的

我们可以强行让它可以修改，就像DP一样，可以强行加上一维时间维,表示这次操作的时间。

即把询问[l,r]变成[l,r,time]

那么我们的坐标也可以在时间维上移动，即[l,r,time]多了一维可以移动的方向，可以变成：

• [l-1,r,time]
• [l+1,r,time]
• [l,r-1,time]
• [l,r+1,time]
• [l,r,time-1]
• [l,r,time+1]

这样的转移也是O(1)的，但是我们排序又多了一个关键字，再搞搞就行了

可以用和普通莫队类似的方法排序转移，做到O(n^{\frac{5}{3}})

这一次我们排序的方式是以n^{\frac{2}{3}}为一块，分成了n^{\frac{1}{3}}块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。

还是来证明一下时间复杂度（默认块大小为n^\frac{2}{3}）：

• 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是O(n)

• 若左右端点所在块改变，时间一次最多会移动n个格子，时间复杂度O(n)

• 左端点所在块一共有n^{\frac{1}{3}}中，右端点也是n^{\frac{1}{3}}种，一共{n^{\frac{1}{3}}}\times{n^{\frac{1}{3}}}=n^{\frac{2}{3}}种，每种乘上移动的复杂度O(n)，总复杂度O(n^{\frac{5}{3}})

树上莫队

莫队只能处理线性问题，我们要把树强行压成一维的

我们可以将树的括号序跑下来，把括号序分块，在括号序上跑莫队

具体怎么做呢？

dfs一棵树，然后如果dfs到x点，就push_back(x),dfs完x点，就直接push_back(-x)，然后我们在挪动指针的时候

• 新加入的值是x ---> add(x)
• 新加入的值是-x ---> del(x)
• 新删除的值是x ---> del(x)
• 新删除的值是-x ---> add(x)

这样的话，我们就把一棵树处理成了序列。

好像还有对树的连通块分块的方法，不过好像比较难我也不会(

例题是[WC2013]糖果公园,这题是带修改树上莫队

题意是给你一棵树,每个点有颜色,每次询问

\sum_{c}val_c\sum_{i=1}^{cnt_c}w_i

val表示该颜色的价值

cnt表示颜色出现的次数

w表示该颜色出现i次后的价值

先把树变成序列，然后每次添加/删除一个点，这个点的对答案的的贡献是可以在O(1)时间内获得的，即val_c\times w_{cnt_{c+1}}

发现因为他会把起点的子树也扫了一遍，产生多余的贡献，怎么办呢？

因为扫的过程中起点的子树里的点肯定会被扫两次，但贡献为0

所以可以开一个vis数组，每次扫到点x，就把vis_x异或上1

如果vis_x=0，那这个点的贡献就可以不计

所以可以用树上莫队来求

修改的话，加上一维时间维即可,变成带修改树上莫队

然后因为所包含的区间内可能没有LCA，对于没有的情况要将多余的贡献删除，然后就完事了

code：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>

#define DEBUG printf("line:%d func:%s\n",__LINE__,__FUNCTION__);

using namespace std;

const int maxn=200010;

int f[maxn],g[maxn],id[maxn],head[maxn],cnt,last[maxn],dep[maxn],fa[maxn][22],v[maxn],w[maxn];
int block,index,n,m,q;
int pos[maxn],col[maxn],app[maxn];
bool vis[maxn];
long long ans[maxn],cur;

struct edge {
    int to,nxt;
} e[maxn];
int cnt1=0,cnt2=0;//时间戳

struct query {
    int l,r,t,id;
    bool operator <(const query &b)const {
        return (pos[l]<pos[b.l])||(pos[l]==pos[b.l]&&pos[r]<pos[b.r])||(pos[l]==pos[b.l]&&pos[r]==pos[b.r]&&t<b.t);
    }
} a[maxn],b[maxn];

inline void addedge(int x, int y) {
    e[++cnt]=(edge) {
        y,head[x]
    };
    head[x]=cnt;
}

void dfs(int x) {
    id[f[x]=++index]=x;
    for(int i=head[x]; i; i=e[i].nxt) {
        if(e[i].to!=fa[x][0]) {
            fa[e[i].to][0]=x;
            dep[e[i].to]=dep[x]+1;
            dfs(e[i].to);
        }
    }
    id[g[x]=++index]=x;//括号序
}

inline void swap(int &x,int &y) {
    int t;
    t=x;
    x=y;
    y=t;
}

inline int lca(int x,int y) {
    if(dep[x]<dep[y])
        swap(x,y);
    if(dep[x]!=dep[y]) {
        int dis=dep[x]-dep[y];
        for(int i=20; i>=0; i--)
            if(dis>=(1<<i))
                dis-=1<<i,x=fa[x][i];
    }//爬到同一高度 
    if(x==y) return x;
    for(int i=20; i>=0; i--) {
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}

inline void add(int x) {
    if(vis[x])
        cur-=(long long )v[col[x]]*w[app[col[x]]--];
    else
        cur+=(long long )v[col[x]]*w[++app[col[x]]];
    vis[x]^=1;
}

inline void modify(int x,int t) {
    if(vis[x]) {
        add(x);
        col[x]=t;
        add(x);
    } else col[x]=t;
}//在时间维上移动

int main() {
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1; i<=m; i++)
        scanf("%d",&v[i]);
    for(int i=1; i<=n; i++)
        scanf("%d",&w[i]);
    for(int i=1; i<n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    for(int i=1; i<=n; i++) {
        scanf("%d",&last[i]);
        col[i]=last[i];
    }
    dfs(1);
    for(int j=1; j<=20; j++)
        for(int i=1; i<=n; i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];//预处理祖先 
    int block=pow(index,2.0/3);
    for(int i=1; i<=index; i++) {
        pos[i]=(i-1)/block;
    }
    while(q--) {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==0) {
            b[++cnt2].l=x;
            b[cnt2].r=last[x];
            last[x]=b[cnt2].t=y;
        } else {
            if(f[x]>f[y])
                swap(x,y);
            a[++cnt1]=(query) {
                lca(x,y)==x?f[x]:g[x],f[y],cnt2,cnt1
            };
        }
    }
    sort(a+1,a+cnt1+1);
    int L,R,T;//指针坐标
    L=R=0;
    T=1;
    for(int i=1; i<=cnt1; i++) {
        while(T<=a[i].t) {
            modify(b[T].l,b[T].t);
            T++;
        }
        while(T>a[i].t) {
            modify(b[T].l,b[T].r);
            T--;
        }
        while(L>a[i].l) {
            L--;
            add(id[L]);
        }
        while(L<a[i].l) {
            add(id[L]);
            L++;
        }
        while(R>a[i].r) {
            add(id[R]);
            R--;
        }
        while(R<a[i].r) {
            R++;
            add(id[R]);
        }
        int x=id[L],y=id[R];
        int llca=lca(x,y);
        if(x!=llca&&y!=llca) {
            add(llca);
            ans[a[i].id]=cur;
            add(llca);
        } else ans[a[i].id]=cur;
    }
    for(int i=1; i<=cnt1; i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

回滚莫队！！

例题: 给定一个序列，多次询问一段区间 [l,r]，求区间中相同的数的最远间隔距离.

当然本题普通莫队也是可以完成的，因为可以预处理每个数的相同前驱后继从而使删除操作变简单，这非常朴素.

考虑到朴素的莫队算法在处理删除操作时会有一些麻烦. 如本题中删除一个元素后更新下一个最远元素的操作肥肠困难. 而利用回滚莫队可以减少删除操作，让更多的操作是插入而非删除.

为了让操作只有插入没有删除，回滚莫队的排序方式是让询问从中心点向左右拓展，覆盖尽量多询问. 重复此操作直至所有询问被处理.