学习笔记

在此膜拜莫涛大佬以及同机房的莫队@Zkl21 。

普通莫队

先来考虑一个极其简单的问题：

1
给你一个序列 a，有多组询问，每次询问 [l, r] 的和

一眼前缀和，但是我们也可以用莫队大材小用地做这道题。

我们可以维护一个左端点 LL 和 RR，我们可以发现，维护了这两个端点以及 [L,R][L, R] 之间的信息之后就可以很轻松的计算出 [L,R+1][L, R + 1]，[L,R−1][L, R - 1]，[L−1,R][L - 1, R]，[L+1,R][L + 1, R] 这些区间的信息，于是就可以每个询问都这么转移。

当然可以构造数据来卡掉它，比如下面的数据：

1
2
3
4
5
6
7
1 1000000
999999 1000000
1 1000000
999999 1000000
1 1000000
999999 1000000
...

每次询问都朴素转移的话，就和暴力没什么区别了，所以我们需要将所有询问离线下来，再排个序，最后按顺序输出即可。

排序方法

这里用的是一种非常简单的排序规则：分块。按照左端点右端点所在块来排序。块长一般取 N\sqrt N，这样可以保证时间复杂度为 O(NN)O(N\sqrt N)。

1
2
3
4
5
bool operator < (const Q& q)
{
    if(pos[l] != pos[q.l]) return pos[l] < pos[q.l];
    return pos[r] < pos[q.r]; 
}

注意

上面说的区间 [L,R][L, R] 向别的区间转移时，有 4 个操作：

1
2
3
4
while(R < q[i].r) add(++ R);
while(L > q[i].l) add(-- L);
while(R > q[i].r) sub(R --);
while(L < q[i].l) sub(L ++);

这四个操作的顺序是有一些讲究的，比如我们现在区间为 [2,4][2, 4]，要转移到 [9,10][9, 10]，假如我们采取了错误的顺序转移，可能会出现例如 [9,4][9, 4] 这样的情况，这时维护的区间为负数，有的时候可能是不会出问题的，但是有时候如果用数据结构维护可能会导致越界等一系列问题，因此我们要采取正确的循环顺序。下面的表是从 OIwiki 上拿过来的，里面有所有的循环顺序以及是否正确：

循环顺序 正确性 反例或注释
l--,l++,r--,r++ 错误 l<r<l′<r′l<r<l'<r'
l--,l++,r++,r-- 错误 l<r<l′<r′l<r<l'<r'
l--,r--,l++,r++ 错误 l<r<l′<r′l<r<l'<r'
l--,r--,r++,l++ 正确 证明较繁琐
l--,r++,l++,r-- 正确
l--,r++,r--,l++ 正确
l++,l--,r--,r++ 错误 l<r<l′<r′l<r<l'<r'
l++,l--,r++,r-- 错误 l<r<l′<r′l<r<l'<r'
l++,r++,l--,r-- 错误 l<r<l′<r′l<r<l'<r'
l++,r++,r--,l-- 错误 l<r<l′<r′l<r<l'<r'
l++,r--,l--,r++ 错误 l<r<l′<r′l<r<l'<r'
l++,r--,r++,l-- 错误 l<r<l′<r′l<r<l'<r'

全部 24 种排列中只有 6 种是正确的，其中有 2 种的证明较繁琐，这里只给出其中 4 种的证明。

这 4 种正确写法的共同特点是，前两步先扩大区间（l-- 或 r++），后两步再缩小区间（l++ 或 r--）。这样写，前两步是扩大区间，可以保持 l≤r+1l\le r+1；执行完前两步后，l≤l′≤r′≤rl\le l'\le r'\le r 一定成立，再执行后两步只会把区间缩小到 [l′,r′][l',r']，依然有 l≤r+1l\le r+1，因此这样写是正确的。

例题

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

这道题要统计区间相同数对的数量，用莫队可以轻松处理。

假设我们知道了 [L,R][L, R] 区间内每种颜色的数量 numnum，当我们要增加一个颜色为 cc 的元素时，相同颜色的数对 cntcnt 会增加 numcnum_c 个，同时再让 numcnum_c 加 11。减去颜色时也同理。

然后每个询问的答案就是 cntiCr−l+12\frac{cnt_i}{C^2_{r - l + 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
int n, m;
int a[N];
int pos[N];

struct Q
{
    int op, l, r;
    bool operator < (const Q& q)
    {
        if(pos[l] != pos[q.l]) return pos[l] < pos[q.l];
        return pos[r] < pos[q.r]; 
    }
}q[N];

struct fraction
{
    //分数结构体
}ans[N];

ll cnt;
int num[N];

void add(int pos)
{
    cnt += num[a[pos]];
    num[a[pos]] ++;
}

void sub(int pos)
{
    num[a[pos]] --;
    cnt -= num[a[pos]];
}

int main()
{
    scanf("%d%d", &n, &m);
    int _ = sqrt(n);
    for(int i = 1; i <= n; i ++ )
    {
        pos[i] = (i - 1) / _;
        scanf("%d", &a[i]);
    }
    
    for(int i = 1; i <= m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }

    sort(q + 1, q + m + 1);

    int L = 1, R = 0;
    for(int i = 1; i <= m; i ++ )
    {
        while(R < q[i].r) add(++ R);
        while(L > q[i].l) add(-- L);
        while(R > q[i].r) sub(R --);
        while(L < q[i].l) sub(L ++);
        if(q[i].l == q[i].r) ans[q[i].op] = {0, 1};
        else
        {
            ans[q[i].op] = {cnt, C(q[i].r - q[i].l + 1, 2)};
            ans[q[i].op].divide();
        }
    }
}

P2709 小B的询问

这个题的信息更好维护，开个桶即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void add(int pos)
{
    res -= (cnt[a[pos]] * cnt[a[pos]]);
    cnt[a[pos]] ++;
    res += (cnt[a[pos]] * cnt[a[pos]]);
}

void sub(int pos)
{
    res -= (cnt[a[pos]] * cnt[a[pos]]);
    cnt[a[pos]] --;
    res += (cnt[a[pos]] * cnt[a[pos]]);
}

struct Q
{
    int l, r, k;
    bool operator < (const Q &q) const
    {
        if(pos[l] == pos[q.l]) return pos[r] < pos[q.r];
        else return pos[l] < pos[q.l];
    }
}q[N];

带修莫队

带修莫队可以处理修改，同时时间复杂度也会相应的增加一部分，一般为 O(n53)O(n^{\frac{5}{3}})。

带修莫队与普通莫队不同的一点是，增加了一维时间 TT，因此我们在每次从 [L,R,T][L, R, T] 向询问 [Li,Ri,Ti][L_i, R_i, T_i] 转移时，首先先将 TT 挪到该询问的时间，同时将 [Ti,T][T_i, T] 或 [T,Ti][T, T_i] 这之间的修改全部撤销或者执行。之后再进行区间左右端点的转移即可。

时间复杂度

带修莫队一般块长取到 n23n^{\frac{2}{3}}，这样可以保证时间复杂度为最优。具体证明我也不会，从 OIwiki 上搬过来的证明见下：

带修莫队排序的第二关键字是右端点所在块编号，不同于普通莫队。

想一想，如果不把右端点分块：

  • 乱序的右端点对于每个询问会移动 nn 次。
  • 有序的右端点会带来乱序的时间，每次询问会移动 tt 次。

无论哪一种情况，带来的时间开销都无法接受。

接下来分析时间复杂度。

设块长为 ss，则有 ns\frac{n}{s} 个块。对于块 ii 和块 jj，记有 qi,jq_{i,j} 个询问的左端点位于块 ii，右端点位于块 jj。

每「组」左右端点不换块的询问 (i,j)(i,j)，端点每次移动 O(s)O(s) 次，时间单调递增，O(t)O(t)。

左右端点换块的时间忽略不计。

表示一下就是：

∑i=1ns∑j=i+1ns(qi,j⋅s+t)=ms+(ns)2t=ms+n2ts2\begin{aligned} &\sum_{i=1}^{\frac{n}{s}}\sum_{j=i+1}^{\frac{n}{s}}(q_{i,j}\cdot s+t)\\ =&ms+(\frac{n}{s})^2t\\ =&ms+\frac{n^2t}{s^2} \end{aligned}

考虑求导求此式极小值。设 f(s)=ms+n2ts2f(s)=ms+\frac{n^2t}{s^2}。那 f′(s)=m−2n2ts3=0f'(s)=m-\frac{2n^2t}{s^3}=0。

得 s=2n2tm3=213n23t13m13=s0s=\sqrt[3]{\frac{2n^2t}{m}}=\frac{2^\frac{1}{3}n^\frac23t^\frac13}{m^\frac13}=s_0。

也就是当块长取 n23t13m13\frac{n^\frac23t^\frac13}{m^\frac13} 时有最优时间复杂度 O(n23m23t13)O(n^\frac23m^\frac23t^\frac13)。

常说的 O(n53)O(n^\frac53) 便是把 n,m,tn,m,t 当做同数量级的时间复杂度。

实际操作中还是推荐设定 n23n^{\frac{2}{3}} 为块长。

例题

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

本题为带修莫队板子题，开个桶维护即可。

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
const int N = 1e6 + 10;
int a[N], pos[N];
int n, m;
struct query
{
    int op, l, r, time;
    bool operator < (const query& Q)
    {
        if(pos[l] == pos[Q.l])
        {
            if(pos[r] == pos[Q.r])
                return time < Q.time;
            return pos[r] < pos[Q.r];
        }
        return pos[l] < pos[Q.l];
    }
}q[N];

int qtt;
struct change
{
    int p, v;
}c[N];

int num[N], ans[N];
int cnt, now;
inline void add(int p)
{
    if(!num[a[p]]) cnt ++;
    num[a[p]] ++;
}

inline void sub(int p)
{
    num[a[p]] --;
    if(!num[a[p]]) cnt --;
}

int main()
{
    n = read(), m = read();
    int _ = pow(n, 2.0 / 3.0);
    
    for(int i = 1; i <= m; i ++ )
    {
        char op[5];
        scanf("%s", op);
        if(op[0] == 'Q')
        {
            int l = read(), r = read();
            qtt ++;
            q[qtt] = {qtt, l, r, i};
        }
        else
        {
            int p = read(), v = read();
            c[i] = {p, v};
        }
    }

    sort(q + 1, q + qtt + 1);

    int L = 1, R = 0;
    for(int i = 1; i <= qtt; i ++ )
    {
        while(now < q[i].time)
        {
            now ++;
            if(c[now].p >= L && c[now].p <= R)
            {
                sub(c[now].p);
                swap(c[now].v, a[c[now].p]);
                add(c[now].p);
            }
            else if(c[now].p) swap(c[now].v, a[c[now].p]);
        }
        while(now > q[i].time)
        {
            if(c[now].p >= L && c[now].p <= R)
            {
                sub(c[now].p);
                swap(c[now].v, a[c[now].p]);
                add(c[now].p);
            }
            else if(c[now].p) swap(c[now].v, a[c[now].p]);
            now --;
        }

        while(R < q[i].r) add(++ R);
        while(L > q[i].l) add(-- L);
        while(R > q[i].r) sub(R --);
        while(L < q[i].l) sub(L ++);
        ans[q[i].op] = cnt;
    }

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

树上莫队

树上莫队一般有两种形式：将树跑出括号序再在括号序上跑莫队、直接在树上跑莫队。接下来先介绍第一种。

补充：括号序

补充这玩意的原因是我直到学这个之前我一直不知道括号序是什么

括号序即为对一颗树进行 dfs 的过程中，刚刚进入时加入一次，在退出时再加入一次，求括号序的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
void dfs1(int u, int father)
{
    id[++ idexx] = u;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs1(j, u);
    }
    id[++ idexx] = u;
}

比如下面这棵树：

iL1jE5.png

它的括号序即为：1,2,3,3,4,4,2,5,5,11, 2, 3, 3, 4, 4, 2, 5, 5, 1

每相同的两个点之间即为该点的子树。

我们把括号标上：(1,(2,(3,3),(4,4),2),(5,5),1)(1, (2, (3, 3), (4, 4), 2), (5, 5), 1)

例题

P4074 [WC2013] 糖果公园

本题将括号序跑下来，再进行一个带修莫队。

用 visuvis_u 表示 uu 该点是否有贡献，出现一次时就将 visuvis_u 异或上 11 即可。

注意：可能两个点括号序之间的点会少一个 lcalca，所以需要特判一个点是否为 lcalca，如果都不是则加上 lcalca 的贡献。同时在对询问进行处理时记得处理好左右端点。

代码：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int h[N], e[N], ne[N], idx;
int v[N], w[N], c[N];
int pos[N];
int n, m, Q;

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

struct query
{
    int op, l, r, time;
    bool operator < (const query& Q) const
    {
        if(pos[l] == pos[Q.l])
        {
            if(pos[r] == pos[Q.r])
                return time < Q.time;
            return pos[r] < pos[Q.r];
        }
        return pos[l] < pos[Q.l];
    }
}q[N];
int qtt;

int last[N];
struct change
{
    int x, last, to;
}ch[N];

int fa[N], dep[N], son[N], siz[N];
int f[N], g[N], idexx;
int id[N];
void dfs1(int u, int father)
{
    f[u] = ++ idexx;
    id[idexx] = u;
    fa[u] = father, dep[u] = dep[father] + 1;
    siz[u] = 1;
    int maxsize = -1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs1(j, u);
        siz[u] += siz[j];
        if(siz[j] > maxsize)
        {
            maxsize = siz[j];
            son[u] = j;
        }
    }
    g[u] = ++ idexx;
    id[idexx] = u;
}

int top[N];
void dfs2(int u, int t)
{
    top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

int tim;

inline int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) return x;
    return y;
}

int L = 1, R = 0, T = 0;
bool vis[N];
ll num[N], ans[N];
ll cnt;
void add(int p)
{
    if(vis[p])
    {
        cnt -= (ll)v[c[p]] * w[num[c[p]]];
        num[c[p]] --;
    }
    else
    {
        num[c[p]] ++;
        cnt += (ll)v[c[p]] * w[num[c[p]]];
    }
    vis[p] ^= 1;
}

void modify(int x, int t)
{
    if(vis[x])
    {
        add(x);
        c[x] = t;
        add(x);
    }
    else c[x] = t;
}

int main()
{
    memset(h, -1, sizeof h);

    n = read(), m = read(), Q = read();
    for(int i = 1; i <= m; i ++ ) v[i] = read();
    for(int i = 1; i <= n; i ++ ) w[i] = read();

    for(int i = 1; i < n; i ++ )
    {
        int a = read(), b = read();
        add(a, b), add(b, a);
    }

    dfs1(1, 1);
    dfs2(1, 1);

    int _ = pow(idexx, 2.0 / 3.0);
    for(int i = 1; i <= idexx; i ++ ) pos[i] = (i - 1) / _;
    
    for(int i = 1; i <= n; i ++ )
    {
        c[i] = read();
        last[i] = c[i];
    }

    for(int i = 1; i <= Q; i ++ )
    {
        int op = read(), x = read(), y = read();
        if(op == 0)
        {
            tim ++;
            ch[tim] = {x, last[x], y};
            last[x] = y;
        }
        else
        {
            qtt ++;
            q[qtt].op = qtt;
            q[qtt].time = tim;
            if(f[x] > f[y]) swap(x, y);
            if(lca(x, y) == x) q[qtt].l = f[x];
            else q[qtt].l = g[x];
            q[qtt].r = f[y];
        }
    }

    sort(q + 1, q + qtt + 1);

    L = 1, R = 0, T = 0;
    for(int i = 1; i <= qtt; i ++ )
    {
        while(T < q[i].time)
        {
            T ++;
            modify(ch[T].x, ch[T].to);
        }
        while(T > q[i].time)
        {
            modify(ch[T].x, ch[T].last);
            T --;
        }
        while(R < q[i].r) add(id[++ R]);
        while(L > q[i].l) add(id[-- L]);
        while(R > q[i].r) add(id[R --]);
        while(L < q[i].l) add(id[L ++]);
        int x = id[L], y = id[R];
        int anc = lca(x, y);
        if(x != anc && y != anc)
        {
            add(anc);
            ans[q[i].op] = cnt;
            add(anc);
        }
        else ans[q[i].op] = cnt;
    }

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

    return 0;
}

树分块

上面所说的仅仅是把树转换成了括号序，本质还是没有变，但是树分块就很有利于直接在树上进行莫队。

先来看一道例题：

P2325 [SCOI2005]王室联邦

将一颗树分为许多部分，要求每部分大小不小于 BB 且不大于 3B3B。

本题可以维护一个栈，在 dfs 的过程中不断往栈中加点，当在某个点 dfs 的过程中子树的大小大于 BB 时，就把子树弹出变成一个块。最后 dfs 一定会有剩下的部分，就把它们放到根上即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int u, int fa)
{
    int sz = stk.size();
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        siz[u] += siz[j];
        if(stk.size() - sz >= lim)
        {
            cnt ++;
            rt[cnt] = u;
            while(stk.size() > sz) b[stk.top()] = cnt, stk.pop();
        }
    }
    stk.push(u);
}

// in main
dfs(1, 1);
while(stk.size()) b[stk.top()] = cnt, stk.pop();

按照这个方式，我们就可以将树进行分块，将询问排序。

真正的树上莫队

我们同样可以维护 22 个指针，每次询问走向目标点，但是这样也会出现问题，比如下图：

i1P5xq.md.jpeg

该图的 L,RL, R 指针都指向了根节点，因此根节点会被算入答案，visroot=truevis_{root} = true。

当指针下移时，看下图：

i1Phwb.md.png

根节点被撤销一次。

i1PGYd.png

根节点再被撤销一次，于是我们的答案中就会增加一项，导致答案错误。

因此我们移动指针时，不要把指针移到各自的 lcalca 处，而是把 lcalca 的答案单独计算。

例题

同上，P4074 [WC2013] 糖果公园

代码如下：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int h[N], e[N], ne[N], idx;
int n, m, Q, lim, bcnt;
ll v[N], w[N];
int c[N], last[N];
int block[N];

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

int fa[N], dep[N], siz[N], son[N];

void dfs1(int u, int f)
{
    int sz = stk.size();
    fa[u] = f, dep[u] = dep[f] + 1;
    siz[u] = 1;
    int maxsize = -1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == f) continue;
        dfs1(j, u);
        siz[u] += siz[j];
        if(siz[j] > maxsize)
        {
            maxsize = siz[j];
            son[u] = j;
        }
        if(stk.size() - sz >= lim)
        {
            bcnt ++;
            while(stk.size() >= sz) 
            {
                block[stk.top()] = bcnt, stk.pop();
            }
        }
    }
    stk.push(u);
}

inline int lca(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) return x;
    return y;
}

struct Query
{
    int op, x, y, tim;
    bool operator < (const Query& q) const
    {
        if(block[x] == block[q.x])
        {
            if(block[y] == block[q.y])
                return tim < q.tim;
            return block[y] < block[q.y];
        }
        return block[x] < block[q.x];
    }
}q[N];
int qt;

struct Change
{
    int x, last, to;
}ch[N];
int TIM;

bool vis[N];
int L = 1, R = 1, T;
ll num = 0, ans[N], cnt[N];

inline void update(int u)
{
    if(vis[u])
    {
        num -= (ll)v[c[u]] * w[cnt[c[u]]];
        cnt[c[u]] --;
    }
    else
    {
        cnt[c[u]] ++;
        num += (ll)v[c[u]] * w[cnt[c[u]]];
    }
    vis[u] ^= 1;
}

inline void move(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    while(dep[x] > dep[y]) update(x), x = fa[x];
    while(x != y) update(x), update(y), x = fa[x], y = fa[y];
}

inline void modify(int x, int t)
{
    if(vis[x])
    {
        update(x);
        c[x] = t;
        update(x);
    }
    else c[x] = t;
}

int main()
{
    memset(h, -1, sizeof h);
    n = read(), m = read(), Q = read();
    lim = pow(n, 0.6);

    for(int i = 1; i <= m; i ++ ) v[i] = read();
    for(int i = 1; i <= n; i ++ ) w[i] = read();

    for(int i = 1; i < n; i ++ )
    {
        int a = read(), b = read();
        add(a, b), add(b, a);
    }

    dfs1(1, 1);
    dfs2(1, 1);

    if(!stk.empty()) 
    {
        bcnt ++;
        while(stk.size()) block[stk.top()] = bcnt, stk.pop();
    }

    for(int i = 1; i <= n; i ++ )
    {
        c[i] = read();
        last[i] = c[i];
    }

    for(int i = 1; i <= Q; i ++ )
    {
        int type = read(), x = read(), y = read();
        if(type == 0)
        {
            TIM ++;
            ch[TIM] = {x, last[x], y};
            last[x] = y;
        }
        else
        {
            qt ++;
            q[qt] = {qt, x, y, TIM};
        }
    }

    for(int i = 1; i <= qt; i ++ )
        if(dfn[q[i].x] > dfn[q[i].y])
            swap(q[i].x, q[i].y);

    sort(q + 1, q + qt + 1);
    for(int i = 1; i <= qt; i ++ )
    {
        while(T < q[i].tim) 
        {
            T ++;
            modify(ch[T].x, ch[T].to);
        }
        while(T > q[i].tim)
        {
            modify(ch[T].x, ch[T].last);
            T --;
        }
        if(L != q[i].x) move(L, q[i].x), L = q[i].x;
        if(R != q[i].y) move(R, q[i].y), R = q[i].y;
        
        int f = lca(L, R);
        
        update(f);
        
        ans[q[i].op] = num;
        update(f);
    }

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

回滚莫队

回滚莫队，又称不删除/能少删点就少删点莫队，它的效果发挥在如果在调整左右端点时，增加十分简单，但是删除很难的话，就可以采用回滚莫队，增加增加的次数，减少删除的次数。

具体方式是这样的：先按左端点所在块排序，再按右端点排序（保证右端点单调递增）。然后对每个询问，把左指针强行拉到该块的右端点，右指针不动，然后让左指针往左跑，右指针接着往右跑，记录答案即可。回答完一个块内的询问后就可以直接拉到下一个块了。

这里我们按照右端点排序，因此右端点的信息是单调增加的，因此我们就可以在撤回左端点时把答案再还原成块右端点到当前询问的右端点区间内。

例题

P5906 【模板】回滚莫队&不删除莫队

本题作为板子题，可以轻松拿回滚莫队 AC。

回答每个块内的询问时，记录右端点数的第一次出现和最后一次出现，按块的右端点 midmid，答案可分为 3 类：在 [L,mid][L, mid]，右区间 [mid+1,R][mid + 1, R]，以及横跨。第一种和第三种统计起来很简单，但第二种回撤左指针时注意判断是否会把在右区间的信息给弄没。

代码：

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
#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 10;
int a[N], pos[N];
queue<int> change;
vector<int> nums;
int t[N];
int n, m, bn;
int st[N], ma[N], ans[N], last[N];

struct query
{
    int op, l, r;
    bool operator < (const query& Q) const
    {
        if(pos[l] == pos[Q.l]) return r < Q.r;
        return pos[l] < pos[Q.l];
    }
}q[N];

int calc(int l, int r)
{
    int res = 0;
    for(int i = l; i <= r; i ++ ) last[a[i]] = 0;
    for(int i = l; i <= r; i ++ ) 
        if(!last[a[i]]) last[a[i]] = i;
        else res = max(res, i - last[a[i]]);
    return res;
}

int main()
{
    n = read();

    int _ = sqrt(n);
    for(int i = 1; i <= n; i ++ ) 
    {
        a[i] = read();
        nums.push_back(a[i]);
        pos[i] = (i - 1) / _ + 1;
    }

    bn = pos[n];

    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();
    
    m = read();
    for(int i = 1; i <= m; i ++ )
    {
        int l = read(), r = read();
        q[i] = {i, l, r};
    }

    sort(q + 1, q + m + 1);
    for(int i = 1, j = 0; i <= m; j ++ )
    {
        int br = min(n, j * _), l = br + 1, r = l - 1, cnt = 0;
        for(; pos[q[i].l] == j; i ++ )
        {
            if(pos[q[i].l] == pos[q[i].r])
            {
                ans[q[i].op] = calc(q[i].l, q[i].r);
                continue;
            }
            while(r < q[i].r)
            {
                r ++;
                ma[a[r]] = r;
                if(!st[a[r]]) st[a[r]] = r, change.push(a[r]);
                cnt = max(cnt, r - st[a[r]]);
            }
            int tp = cnt;
            while(l > q[i].l)
            {
                l --;
                if(ma[a[l]]) cnt = max(cnt, ma[a[l]] - l);
                else ma[a[l]] = l;
            }
            ans[q[i].op] = cnt;
            while(l <= br)
            {
                if(ma[a[l]] == l) ma[a[l]] = 0;
                l ++;
            }
            cnt = tp;
        }
        while(change.size()) st[change.front()] = ma[change.front()] = false, change.pop();
    }

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

歴史の研究

本题感觉更适合作为板子题来使，思路同上，回滚莫队搞定。

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
#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

const int N = 1e6 + 10;
ll a[N], pos[N], ans[N];
ll cntt[N], imt[N];
queue<ll> change;
vector<ll> nums;
int n, m;
ll imp[N], cnt[N];

struct query
{
    int op, l, r;
    bool operator < (const query& q) const
    {
        if(pos[l] == pos[q.l]) return r < q.r;
        return pos[l] < pos[q.l];
    }
}q[N];

inline ll get(int x)
{
    return nums[x];
}

inline ll calc(int l, int r)
{
    ll res = 0;
    for(int i = l; i <= r; i ++ ) cntt[a[i]] = imt[a[i]] = 0;
    for(int i = l; i <= r; i ++ )
    {
        imt[a[i]] -= get(a[i]) * cntt[a[i]];
        cntt[a[i]] ++;
        imt[a[i]] += get(a[i]) * cntt[a[i]];
        res = max(res, imt[a[i]]);
    }
    return res;
}

signed main()
{
    n = read(), m = read();

    int _ = sqrt(n);
    for(int i = 1; i <= n; i ++ ) 
    {
        a[i] = read();
        nums.push_back(a[i]);
        pos[i] = (i - 1) / _ + 1;
    }

    int bn = pos[n];

    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; i <= m; i ++ )
    {
        int l = read(), r = read();
        q[i] = {i, l, r};
    }

    sort(q + 1, q + 1 + m);

    for(int i = 1, j = 0; j <= bn; j ++ )
    {
        int br = min(n, _ * j), l = br + 1, r = l - 1, ANSIMP = 0;
        for(; pos[q[i].l] == j; i ++ )
        {
            if(pos[q[i].l] == pos[q[i].r])
            {
                ans[q[i].op] = calc(q[i].l, q[i].r);
                continue;
            }
            while(r < q[i].r)
            {
                r ++;
                change.push(a[r]);
                cnt[a[r]] ++;
                imp[a[r]] += get(a[r]);
                if(ANSIMP < imp[a[r]])
                {
                    ANSIMP = imp[a[r]];
                }
            }
            int lstimp = ANSIMP;
            while(l > q[i].l)
            {
                l --;
                change.push(a[l]);
                cnt[a[l]] ++;
                imp[a[l]] += get(a[l]);
                if(ANSIMP < imp[a[l]])
                {
                    ANSIMP = imp[a[l]];
                }
            }
            ans[q[i].op] = ANSIMP;
            ANSIMP = lstimp;
            while(l <= br)
            {
                cnt[a[l]] --;
                imp[a[l]] -= get(a[l]);
                l ++;
            }
        }
        while(change.size()) cnt[change.front()] = imp[change.front()] = 0, change.pop();
    }

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

二次离线莫队

二次离线莫队适用于满足下列条件的题：

  1. 可以用莫队
  2. 转移时间复杂度无法承受，例如 O(log⁡n)O(\log n) 或者更高
  3. 答案可表示为 f[x,[1,r]]−f[x,[1,l−1]]f[x, [1, r]] - f[x, [1, l - 1]] 的形式

我们可以在莫队转移的过程中把转移当作询问记录下来，然后在对这些转移用扫描线扫一遍，就可以得出答案了。

例题

P4887 【模板】莫队二次离线

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10, M = 20010;
int a[N], t[N], pos[N], pre[N];
ll ans[N];
int n, m, k;

struct query
{
    int op, l, r;
    ll ans;
    bool operator < (const query& q) const
    {
        if(pos[l] == pos[q.l]) return r < q.r;
        return l < q.l;
    }
}q[N];

struct query2
{
    int l, r, id;
};

vector<query2> v[N];
vector<int> buf;
int L = 1, R = 0;

int main()
{
    n = read(), m = read(), k = read();

    if(k > 14)
    {
        for(int i = 1; i <= m; i ++ ) puts("0");
        return 0;
    }

    int _ = sqrt(n);
    for(int i = 1; i <= n; i ++ ) 
    {
        a[i] = read();
        pos[i] = (i - 1) / _ + 1;
    }

    for(int i = 1; i <= m; i ++ )
    {
        int l = read(), r = read();
        q[i] = {i, l, r, 0};
    }

    for(int i = 0; i < 16384; i ++ ) 
        if(__builtin_popcount(i) == k)
            buf.push_back(i);
    
    for(int i = 1; i <= n; i ++ )
    {
        for(auto x : buf) t[a[i] ^ x] ++;
        pre[i] = t[a[i + 1]];
    }

    sort(q + 1, q + 1 + m);

    memset(t, 0, sizeof t);

    for(int i = 1; i <= m; i ++ )
    {
        int l = q[i].l, r = q[i].r;
        if(R < r) v[L - 1].push_back({R + 1, r, -i});
        while(R < r) {q[i].ans += pre[R]; R ++ ;}
        if(L > l) v[R].push_back({l, L - 1, i});
        while(L > l) {q[i].ans -= pre[L - 2]; L --;}
        if(R > r) v[L - 1].push_back({r + 1, R, i});
        while(R > r) {q[i].ans -= pre[R - 1]; R --;}
        if(L < l) v[R].push_back({L, l - 1, -i});
        while(L < l) {q[i].ans += pre[L - 1]; L ++;}
    }

    for(int i = 1; i <= n; i ++ )
    {
        for(auto x : buf) t[x ^ a[i]] ++;
        for(auto x : v[i])
        {
            int l = x.l, r = x.r, id = x.id;
            for(int j = l; j <= r; j ++ )
            {
                int tmp = t[a[j]];
                if(j <= i && k == 0) tmp --;
                if(id < 0) q[-id].ans -= tmp;
                else q[id].ans += tmp;
            }
        }
    } 

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

后记

莫队系列也差不多肝完了，也花了三四天的时间，同时借鉴了 OIwiki 上的许多内容以及洛谷许多大佬的题解（甚至最后一道板子题都快成赫的了），十分感谢以及膜拜 %%%。