mydcwfy's Blog

莫队

Posted on
Symbols count in article: 12k Reading time ≈ 27 mins.

离线的区间统计一类问题的利器。

莫队

1. 朴素莫队

就是优化暴力，当你不知道怎么做时，就可以考虑莫队了。

2. 例题

我们从例题中学习。

T1：HH的项链

题目传送门 AcWing

题目传送门 Luogu

这道题是模板莫队题。

首先考虑朴素（暴力），就是直接用 Hash 统计出现次数，并且输出即可。

时间复杂度为 $O(mn+ms)$ （s 表示颜色的总数）。

当然可以不用扫描整个数组，如果没统计过的话，就 ans 加一。

时间复杂度为 $O(mn)$。

继续考虑优化。

我们还没有充分利用以前的信息。

比如从 $[i_1\sim j_1]$ 到 $[i_2\sim j_2]$，我们可以使用指针，从 $i_1$ 移动到 $i_2$，并统计，从 $j_1$ 移动到 $j_2$，统计后，在扫描（也可以实时统计）。

于是现在我们关心的就是 $|i_1-i_2|$ 和 $|j_1-j_2|$，但是最坏情况仍然为 $O(n)$，没有得到优化。

现在就要搬出我们的大法——莫队算法！

莫队算法是一种离线算法，它通过对询问进行适当的排序降低复杂度。

我们既要使左边走的小，又要使右边走的小，要平衡两个距离，

就是分块算法！

回忆分块算法，我们要平衡块的长度和块的个数，于是就有了分块。

所以说，莫队实质就是一种分块。

排序需要有两个关键字，第一关键字是左端点所在块编号，第二是右端点。

注意，我们是用左端点分块排序！

设块的长度为 T，则单次左端点移动的复杂度为 $O(T)$，在同一块中，右端点移动的复杂度为 $O(n)$。

总时间复杂度为 $O(Tm+\dfrac{n^2}{T})$.

在 $T=\sqrt{\dfrac{n^2}{m}}$ 时取得最小值，即为 $O(n\sqrt m)$。

另外，还有一个 玄学 优化，就是奇数块递增排序，偶数块递减排序，就可以使右端点走的距离少一些。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;

const int N=1e6+10;

struct Query{
    int l,r,id;
}q[N];

int n,m,len,ans[N],cnt[N],a[N];

inline int get(re int x)
{
    return x/len;
}

inline bool cmp(const Query &a,const Query &b)
{
    int i=get(a.l),j=get(b.l);
    if (i!=j) return i<j;
    return (a.r<b.r)^(i&1);
}

inline void add(re int x,int &res)
{
    if (!cnt[a[x]]) res++;
    cnt[a[x]]++;
}

inline void del(re int x,int &res)
{
    cnt[a[x]]--;
    if (!cnt[a[x]]) res--;
}

inline void read(re int &x)
{
    char c;
    while ((c=getchar())<'0'||c>'9') ;
    x=c-'0';
    while ((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';
}

int main()
{
    read(n);
    for (re int i=1;i<=n;++i) read(a[i]);
    read(m);
    len=1620;
    for (re int i=1;i<=m;++i)
    {
        read(q[i].l),read(q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    re int res=0;
    for (re int i=1,l=1,r=0;i<=m;++i)
    {
        while (l>q[i].l) add(--l,res);
        while (l<q[i].l) del(l++,res);
        while (r<q[i].r) add(++r,res);
        while (r>q[i].r) del(r--,res);
        ans[q[i].id]=res;
    }
    for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

洛谷上数据有点强，莫队现在过不了。

3. 带修改的莫队

将一维转化为二维，另一维是时间轴。

l 到 r 的维护仍然简单，现在我们来讨论当 t 变化时的维护：

如果是不在该区间内的话，我们就直接不管。

如果在的话，就直接加。

但是这里有个问题：怎样修改而不覆盖原来的数？

有一个比较取巧的方法：经过该操作时，直接将原数组的数与修改的数交换。

这样以便于我们回来时可以覆盖回来。

下面一个问题是：怎样排序？

显而易见的方法是：按三个关键字排序，分别为 l 所在编号，r 所在编号，t。

t 表示走到了第几次修改操作，设总修改操作为 t.

设块的大小为 T,则下面三种的复杂度为：

l:$O(Tm)$,r:$O(Tm+\dfrac{n^2}{T})$,t:$O(\dfrac{n^2t}{T^2})$

其中，l 单次移动复杂度为 $O(T)$，r 在同一块单次复杂度为 $O(T)$,区间内移动为 $O(n)$，有 $\dfrac{n}{T}$ 个，t 每一小块为 $O(t)$。

一般 n 和 m 同级别，当 $Tm+\dfrac{n^2}{T}=\dfrac{n^2t}{T}$，即 $Tn=\dfrac{n^2t}{T},T=\sqrt[3]{nt}$，总复杂度最小，为 $O(\sqrt[3]{n^4t})$。

4. 例题

T2：[国家集训队]数颜色 / 维护队列

题目传送门 Luogu

题目传送门 AcWing

上面的模板题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;

const int N=1.5e5+10,M=1e6+10;

struct Query{
    int id,l,r,t;
}q[N];

struct Modify{
    int pos,t;
}c[N];

int ans[N],cnt[M],n,m,cm,qm,len,a[N];

inline int get(re int x)
{
    return x/len;
}

inline bool cmp(const Query &a,const Query &b)
{
    re int i1=get(a.l),i2=get(b.l);
    re int j1=get(a.r),j2=get(b.r);
    if (i1!=i2) return i1<i2;
    if (j1!=j2) return j1<j2;
    return a.t<b.t;
}

inline void add(re int a,int &res)
{
    if (!cnt[a]) res++;
    cnt[a]++;
}

inline void del(re int a,int &res)
{
    cnt[a]--;
    if (!cnt[a]) res--;
}

inline void read(re int &x)
{
    char c;
    while ((c=getchar())<'0'||c>'9') ;
    x=c-'0';
    while ((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';
}

int main()
{
    read(n);read(m);
    for (re int i=1;i<=n;++i) read(a[i]);
    for (re int i=1;i<=m;++i)
    {
        re char op[2];re int a,b;
        scanf("%s",op);
        read(a);read(b);
        if (op[0]=='Q') ++qm,q[qm]=(Query){qm,a,b,cm};
        else ++cm,c[cm]=(Modify){a,b};
    }
    len=pow((double)n*cm,1.0/3.0);//pow((double)n*n,1.0/3.0)
    sort(q+1,q+qm+1,cmp);
    re int res=0;
    for (re int k=1,i=1,j=0,tnow=0;k<=qm;++k)
    {
        re int id=q[k].id,l=q[k].l,r=q[k].r,t=q[k].t;
        while (i>l) add(a[--i],res);
        while (i<l) del(a[i++],res);
        while (j<r) add(a[++j],res);
        while (j>r) del(a[j--],res);
        while (tnow<t)
        {
            ++tnow;
            if (c[tnow].pos>=i&&c[tnow].pos<=j)
            {
                del(a[c[tnow].pos],res);
                add(c[tnow].t,res);
            }
            swap(a[c[tnow].pos],c[tnow].t);
        }
        while (tnow>t)
        {
            if (c[tnow].pos>=i&&c[tnow].pos<=j)
            {
                del(a[c[tnow].pos],res);
                add(c[tnow].t,res);
            }
            swap(a[c[tnow].pos],c[tnow].t);
            tnow--;
        }
        ans[id]=res;
    }
    for (re int i=1;i<=qm;++i) printf("%d\n",ans[i]);
    return 0;
}

5. 回滚莫队

可以发现，有一些莫队，加入操作很好操作，但是删除却不是，所以我们要使用回滚莫队。

我们还是以一道题来看：

T2：[JOI2013]历史研究

题目传送门 Luogu(AtCoder-RemoteJudge)

题目传送门 AcWing

这道题要维护重要度的最大值，由于如果删除，不好维护最大值。

处理当前块的询问。

如果右端点在该块里，直接暴力即可，复杂度为 $O(\sqrt n)$。

如果不在的话，维护下一块开始节点开始的 cnt，的由于右端点是递增，走到每一个询问时直接再暴力加入块内的长度暴力即可。

画个图，其实就是同一块内的每个询问单独处理，块外的一起处理。

可以看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;

typedef long long ll;
const int N=2e5+10;

struct Query{
    int id,l,r;
}q[N];

int a[N],n,len,m,cnt[N];
ll ans[N];
vector <int> nums;

int get(int x)
{
    return x/len;
}

bool cmp(const Query &a,const Query &b)
{
    int i=get(a.l),j=get(b.l);
    if (i!=j) return i<j;
    return a.r<b.r;
}

void add(int a,ll &res)
{
    cnt[a]++;
    res=max(res,(ll)nums[a]*cnt[a]);
}

int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",a+i),nums.push_back(a[i]);
    for (int i=1;i<=m;++i) scanf("%d %d",&q[i].l,&q[i].r);
    for (int i=1;i<=m;++i) q[i].id=i;

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for (int i=1;i<=n;++i) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin();
    
    len=sqrt(n);
    sort(q+1,q+m+1,cmp);
    
    for (int x=1;x<=m;)
    {
        int y=x;
        while (y<=m&&get(q[y].l)==get(q[x].l)) y++;
        int node=get(q[x].l)*len+len-1;
        
        while (x<=m&&q[x].r<=node)
        {
            ll res=0;
            for (int i=q[x].l;i<=q[x].r;++i) add(a[i],res);
            ans[q[x].id]=res;
            for (int i=q[x].l;i<=q[x].r;++i) cnt[a[i]]--;
            x++;
        }

        ll res=0;int j=node;
        while (x<y)
        {
            int l=node+1,r=q[x].r;
            while (j<r) add(a[++j],res);
            ll bac=res;
            for (int k=q[x].l;k<=node;++k) add(a[k],res);
            ans[q[x].id]=res;
            for (int k=q[x].l;k<=node;++k) cnt[a[k]]--;
            res=bac;
            x++;
        }
        memset(cnt,0,sizeof cnt);
    }

    for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}

6. 树上莫队

T3：树上计数2

题目传送门 AcWing

和 HH 的项链 类似，这也是统计当前不同的个数。

主要区别是怎样在树上操作？

这里我们要使用一种序列：欧拉序列。

欧拉序列实现过程就是先写当前节点，遍历完子树后，写一遍当前序列。

很明显的性质是：每一个点都写了两遍。

怎样将树上的序列转化为欧拉序列呢？

对于每一个节点，我们记录两个：$first[u]$ 表示第一次出现的位置，$last[u]$ 表示最后一次出现的位置。

现在要找 $(x,y)(first[x]<fisrt[y])$ 的路径，分为以下两种情况：

  1. $\operatorname{lca}(x,y)=x$ ，则 $[first[x],first[y]]$ 序列中出现一次的点。
  2. $\operatorname{lca}(x,y)\not=x$，则 $[last[x],first[y]]$ 中出现一次的点加上 $\operatorname{lca}(x,y)$ 就是该点。

于是，我们就变成的统计在一个序列中，只出现一次的点不同颜色的点的个数。

在原来的莫队上，我们可以再加一个数组，表示出现了几次。

还有，不论是 add 还是 del，都是对出现次数异或 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

const int N=1e5+10,M=2e5+10,L=20;

struct Query{
    int id,l,r,L;
}q[N];

int a[N],n,m,len,fi[N],la[N],top,dep[N];
int euler[M],ans[N];
int cnt[N],tim[N];
int h[N],e[M],ne[M],idx,f[N][L+1];

vector <int> nums;

int get(int x)
{
    return x/len;
}

bool cmp(const Query &a,const Query &b)
{
    int i=get(a.l),j=get(b.l);
    if (i!=j) return i<j;
    return a.r<b.r;
}

void add_edge(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int x,int fa)
{
    f[x][0]=fa;
    fi[x]=++top;euler[top]=x;
    dep[x]=dep[fa]+1;
    for (int i=1;i<=L;++i) f[x][i]=f[f[x][i-1]][i-1];

    for (int i=h[x];~i;i=ne[i])
        if (!f[e[i]][0]) dfs(e[i],x);
    la[x]=++top;euler[top]=x;
}

int lca(int x,int y)
{
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=L;i>=0;--i)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    
    for (int i=L;i>=0;--i)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

void add(int pos,int &res)
{
    tim[pos]^=1;
    if (tim[pos])
    {
        if (!cnt[a[pos]]) res++;
        cnt[a[pos]]++;
    }
    else
    {
        cnt[a[pos]]--;
        if (!cnt[a[pos]]) res--;
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    
    for (int i=1;i<=n;++i) nums.push_back(a[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for (int i=1;i<=n;++i) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin();

    for (int i=1,a,b;i<n;++i)
    {
        scanf("%d %d",&a,&b);
        add_edge(a,b);add_edge(b,a);
    }
    dfs(1,1);
    len=sqrt(top);

    for (int i=1,a,b;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        if (fi[a]>fi[b]) swap(a,b);
        int l=lca(a,b);
        if (l==a) q[i]=(Query){i,fi[a],fi[b]};
        else q[i]=(Query){i,la[a],fi[b],l};
    }

    sort(q,q+m,cmp);

    for (int k=1,i=1,j=0,res=0;k<=m;++k)
    {
        int l=q[k].l,r=q[k].r,id=q[k].id,p=q[k].L;
        while (i>l) add(euler[--i],res);
        while (i<l) add(euler[i++],res);
        while (j<r) add(euler[++j],res);
        while (j>r) add(euler[j--],res);
        if (p) add(p,res);
        ans[id]=res;
        if (p) add(p,res);
    }

    for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

7. 二次离线莫队

T4：二次离线莫队

题目传送门 Luogu

题目传送门 AcWing

二次离线，顾名思义，就是一次后再离线一次。

假设要从 $[L,R]$ 到 $[l,r]$，且 $r>R$。

我们要将 $[L,R]$ 扩展到 $[L,R+1]$，需要知道 $[L,R]$ 与 R+1 的配对数。

又可以改为前缀和 $ans{[L,R]}=s[R]-s[L-1]$。

首先考虑第一种询问。

其中 $s[R]$ 表示与 R+1 的配对个数，可以改为 $f(R)$。

可以改写为 $g(x)$，表示前 i 个数与 x 配对的数（注意，i 一直在变化）。

现在考虑如何计算，可以发现其实就是开始有 k 个 1 的数与当前数进行异或，得到的数就是需要更新的数。

具体的，如果用 $a_i$ 表示所有是 k 个一的数，x 是当前数，那么 $a_i$^x 就是我们要找的 $b_i$，因为 $b_i$^x=$a_i$。

现在我们就维护好了 $g(x)$，而且可以一直更新。

下面，我们考虑维护 $s[L-1]$。

问题转化为 $[1,L-1]$ 与 $[R+1,r]$ 的配对数。

进行第二次离线，我们首先将所有的询问存起来。

观察到 $[1,L-1]$ 只有一个参量，我们考虑枚举该参量并暴力求。

像上面一样，我们也同时维护 $g(x)$，表示前 i 个数与 x 的配对数。

该询问的复杂度就是 $O(r-R)$，是区间长度的线性复杂度。总时间复杂度为 $O(n\sqrt n)$。

至此，得到解决！

其他的变化，请读者自行推导。

当然也可以看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define lowbit(x) (x&-x)
using namespace std;

typedef long long ll;
const int N=1e5+10,M=(1<<14)+10;

int f[N],g[M];
int a[N],n,m,k,len;
ll ans[N];

struct Query{
    int id,l,r;
    ll res;
}q[N];

struct Range{
    int id,l,r,t;
};

vector <Range> rg[N];
vector <int> nums;

int get(int x)
{
    return x/len;
}

bool cmp(const Query &a,const Query &b)
{
    int i=get(a.l),j=get(b.l);
    if (i!=j) return i<j;
    return a.r<b.r;
}

int get_count(int x)
{
    int res=0;
    while (x)
    {
        res++;
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=m;++i) q[i].id=i;
    for (int i=1;i<=m;++i) scanf("%d %d",&q[i].l,&q[i].r);
    
    for (int i=0;i<(1<<14);++i)
        if (get_count(i)==k) nums.push_back(i);
    for (int i=1;i<=n;++i)
    {
        for (int j=0;j<nums.size();++j) g[nums[j]^a[i]]++;
        f[i]=g[a[i+1]];
    }

    len=sqrt(n);
    sort(q+1,q+m+1,cmp);

    for (int i=1,L=1,R=0;i<=m;++i)
    {
        int l=q[i].l,r=q[i].r;
        ll &res=q[i].res;

        if (R>r) rg[L-1].push_back((Range){i,r+1,R,1});
        while (R>r) res-=f[--R];
        if (R<r) rg[L-1].push_back((Range){i,R+1,r,-1});
        while (R<r) res+=f[R++];
        if (L>l) rg[R].push_back((Range){i,l,L-1,1});
        while (L>l) res-=f[L-2]+!k,L--;
        if (L<l) rg[R].push_back((Range){i,L,l-1,-1});
        while (L<l) res+=f[L-1]+!k,L++;
    }

    memset(g,0,sizeof g);
    for (int i=1;i<=n;++i)
    {
        for (int j=0;j<nums.size();++j) g[nums[j]^a[i]]++;
        for (int j=0;j<rg[i].size();++j)
        {
            Range &tmp=rg[i][j];
            for (int x=tmp.l;x<=tmp.r;++x) q[tmp.id].res+=g[a[x]]*tmp.t;
        }
    }

    for (int i=2;i<=m;++i) q[i].res+=q[i-1].res;
    for (int i=1;i<=m;++i) ans[q[i].id]=q[i].res;

    for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}