#include<codesonic>

#include<codesonic>

using namespace 绿一色;

莫队算法初探

posted on 2018-08-15 19:31:30 | under 学习笔记 |

普通莫队

莫队算法(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}}}$ 反而会快一些(大约是原来的0.9倍)

(如何证明我也不清楚)

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

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;
}