跳转至

莫队

普通莫队

考虑一共有 \(n\) 此询问区间 \([l_i,r_i]\) 上的信息，并且能够在 \(\mathcal O(1)\) 的时间内由 \([l_i,r_i]\) 迭代出: \([l_i+1,r_i]\), \([l_i-1,r_i]\), \([l_i,r_i-1]\), \([l_i,r_i+1]\) 。

那么此时我们按照 \(len = \sqrt{n}\) 分块 ,然后以 \(l\) 所在的块为第一关键字，以 \(r\) 为第二关键字，把询问进行排序。

此时我们按照这个顺序暴力转移，可以证明时间复杂度为 \(\mathcal O(n\sqrt n)\) 。

时间复杂度证明

首先我们考虑左指针：

如果是在块内的移动，每一次最多移动 \(\sqrt n\) 次，所以一共 \(n \sqrt n\) 次。

如果是块之间移动，那么一次最懂移动 \(2\sqrt n\) ，所以一共移动 \(\left(\sqrt n \right)^2 = n\) 。

然后是右指针：

块内因为被排序过，所以总共移动最多: \(n \sqrt n\) 次。

块之间每一次最多 \(n\) 次，所以一共 \(n \sqrt n\) 次。

因此可以得到总时间复杂度为 \(\mathcal O (n\sqrt n)\) 。

一个小优化：

观察下面这个数据1：

1
2
3
4
5
// 设块的大小为 2 (假设)
1 1
2 100
3 1
4 100

此时我们发现处理了第一二个之后来到了: \([2,100]\) 。

此时我们只需要操作两次就可以变成 \([4,100]\) ，但是按照现在的程序会先到 \([3,1]\) 非常的浪费。

所以我们可以考虑一个整块升序，一个降序。

代码：P1494 [国家集训队] 小 Z 的袜子 
 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
#include <bits/stdc++.h>
typedef long long ll;
#define PII pair<ll,ll>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=5e4+5;
int n, m;
int c[N];
int len;
PII ans[N];

struct que {
    int id, l, r;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if((l/len)&1) return r<oth.r;
        else return r>oth.r;
    }
}a[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
ll sum=0, cnt[N];
void add(int x) { sum+=cnt[x], cnt[x]++;}
void del(int x) { cnt[x]--, sum-=cnt[x];}
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n>>m;

    for(int i=1; i<=n; i++) cin>>c[i];
    for(int i=1; i<=m; i++) {
        int l, r; cin>>l>>r;
        a[i]=que{i, l, r};
    }

    len=(int)ceil(sqrt(n));
    sort(a+1, a+m+1);

    for(int i=1, l=1, r=0; i<=m; i++) {
        if(a[i].l==a[i].r) {
            ans[a[i].id]=PII{0,1};
            continue;
        }

        while(l>a[i].l) add(c[--l]);
        while(r<a[i].r) add(c[++r]);
        while(r>a[i].r) del(c[r--]);
        while(l<a[i].l) del(c[l++]);

        ans[a[i].id] = PII{
            sum,
            (ll)(a[i].r-a[i].l+1) * (a[i].r-a[i].l) / 2
        };
    }

    for(int i=1; i<=m; i++) {
        ll gcd = __gcd(ans[i].first, ans[i].second);
        if(gcd>1) {
            ans[i].first/=gcd;
            ans[i].second/=gcd;
        }
        printf("%lld/%lld\n", ans[i].first, ans[i].second);
    }

    return 0;
}

带修莫队

对于待修莫队，其实就是增加了一个时间维度。

此时依然相邻状态可以 \(O(1)\) 转移，此时我们令块长为 \(n^{\frac{2}{3}}\) 。

然后通过下面的函数排序：

1
2
3
4
5
bool operator < (const que& oth) const {
    if(l/len != oth.l/len) return l<oth.l;
    if(r/len != oth.r/len) return r<oth.r;
    return t<oth.t; 
}

此时可以证明时间复杂度为 \(\mathcal O(n^{\frac{5}{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
#include <bits/stdc++.h>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=1e6+5;
int n,m;
int c[N];
int ans[N];

int len;
int cnt1=0, cnt2=0;
struct que {
    int l, r, t, id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if(r/len != oth.r/len) return r<oth.r;
        return t<oth.t; 
    }
}a[N];

struct upde {
    int p,c;
}b[N];

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
int sum=0, cnt[N];
void add(int x) {
    if(cnt[x]==0) sum++;
    cnt[x]++;
}
void del(int x) {
    cnt[x]--;
    if(cnt[x]==0) sum--;
}

/// `x` 代表时间， `y` 代表当前处理i
void cha(int x, int y) {
    if(a[y].l<=b[x].p && b[x].p<=a[y].r) {
        add(b[x].c);
        del(c[b[x].p]);
    }
    swap(c[b[x].p], b[x].c);
}
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>c[i];

    for(int i=1; i<=m; i++) {
        char op; cin>>op;
        if(op=='Q') {
            int l, r; cin>>l>>r;
            a[++cnt1]=que{l,r,cnt2,cnt1};
        } else {
            int p, c; cin>>p>>c;
            b[++cnt2]=upde{p,c};
        }
    }

    len=ceil(pow(n, 2./3));
    sort(a+1, a+cnt1+1);

    for(int i=1, l=1, r=0, t=0; i<=cnt1; i++) {
        while(l>a[i].l) add(c[--l]);
        while(r<a[i].r) add(c[++r]);
        while(l<a[i].l) del(c[l++]);
        while(r>a[i].r) del(c[r--]);
        while(t<a[i].t) cha(++t, i);
        while(t>a[i].t) cha(t--, i);
        ans[a[i].id]=sum;
    }

    for(int i=1; i<=cnt1; i++) {
        cout<<ans[i]<<'\n';
    }

    return 0;
}

树上莫队

括号序列树上莫队

由于普通莫队只能处理序列上的问题，所以我们考虑把树转化为括号序列。

对于一次 DFS ，到达一个点时把 \(x\) 加入，走的时候把 \(x\) 加入。

然后每当我们插入和删除一个节点的时候，我们统计一个 \(vis\) 为他是否已经被计算贡献。

如果已经计算过了，就减去 \(c_x\) ，否则加上。

加上一次询问我们需要查询 \(x \to y\) 路径上的信息，那么分两种情况：

  • \(lca(x,y)=x\) 此时 \(x\) 为 \(y\) 的祖先，那么相当于查询括号序列中 \([in_x,in_y]\) 。

  • \(\texttt{otherwise}\) , 此时相当于查询 \([out_x,in_y] + lca\) 。

参考代码 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
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=1e5+5;
int n, m, q;
int ans[N];
int v[N], w[N], c[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/


int in[N], out[N];
vector<int> arr(1); // 按照DFS顺序的序列
struct LCA {
    vector<int> v[N];

    int cnt;
    int fa[N][20], dep[N];
    void build(int x, int f=0) {
        in[x]=++cnt;
        arr.push_back(x);

        fa[x][0]=f;
        dep[x]=dep[f]+1;
        for(int i=1; i<=19; i++)
            fa[x][i]=fa[fa[x][i-1]][i-1];
        for(auto y: v[x]) {
            if(y==f) continue;
            build(y, x);
        }

        out[x]=++cnt;
        arr.push_back(x);
    }

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

int len;
int cnt1, cnt2;
struct que {
    int l, r, t, lca ,id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        if(r/len != oth.r/len) return r<oth.r;
        return t<oth.t;
    }
}a[N];
pair<int, int> b[N];

int sum, vis[N], cnt[N];
void add(int x) {
    if(!vis[x]) {
        vis[x]=1;
        sum += v[c[x]] * w[++cnt[c[x]]];
    } else {
        vis[x]=0;
        sum -= v[c[x]] * w[cnt[c[x]]--];
    }
}

// 此时的时间 t , 和当前处理的区间 [l,r]
void change(int t, int l, int r) {
    if(vis[b[t].first]) {
        add(b[t].first);
        swap(c[b[t].first], b[t].second);
        add(b[t].first);
    }else swap(c[b[t].first], b[t].second);
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    // stdin
    cin>>n>>m>>q;

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

    for(int i=1; i<n; i++) {
        int x, y; cin>>x>>y;
        lca.v[x].push_back(y);
        lca.v[y].push_back(x);
    }

    for(int i=1; i<=n; i++) cin>>c[i];

    lca.build(1);


    for(int i=1; i<=q; i++) {
        int op, x, y; cin>>op>>x>>y;
        if(op==1) {
            int lc=lca.lca(x, y);
            if(lc==x) a[++cnt1] = que{in[x], in[y], cnt2, 0, cnt1};
            else a[++cnt1] = que{ out[x], in[y], cnt2, lc, cnt1};
        } else {
            b[++cnt2] = make_pair(x, y);
        }
    }

    // solve

    len=ceil(pow(2*n, 2./3));
    sort(a+1, a+cnt1+1);

    for(int i=1, l=1, r=0, t=0; i<=cnt1; i++) {

        while(l>a[i].l) add(arr[--l]);
        while(r<a[i].r) add(arr[++r]);
        while(l<a[i].l) add(arr[l++]);
        while(r>a[i].r) add(arr[r--]);

        while(t<a[i].t) change(++t, l, r);
        while(t>a[i].t) change(t--, l, r);

        if(a[i].lca) add(a[i].lca);
        ans[a[i].id]=sum;
        if(a[i].lca) add(a[i].lca);
    }

    for(int i=1; i<=cnt1; i++) cout<<ans[i]<<'\n';

    return 0;
}

代码细节

通过真是代码可以发现，对于第二种情况可能出现 \(out_x > in_y\) 的情况。

但是其实此时莫队是支持的，因为你不要把莫队当作一个区间，而是一个二维平面上的点: \((x,y)\) ，然后通过 \((x,y)\) 可以得到 \((x,y-1), (x,y+1), (x+1,y), (x-1,y)\) 。

按照这种理解莫队问题其实就变成了找一个路径经过所有的点，要求他们的哈夫曼路径最短。通过分块，就是莫队了。

注意： 写的时候一定要注意传的是括号序列的节点

我们发现这种办法还是有相当的局限性的, 因为他其实只是转换成序列，然后只能且介树上路径的信息。

真 · 树上莫队

%% 等待补充 %%

下面代码有一个快读。

参考代码 
  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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
#include <bits/stdc++.h>
using namespace std;

struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}

~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
char gc() {
#if DEBUG  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
}

void read(int &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
    if (ch == '-') neg = true;
    if (neg)
    for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
}

void read(char *s) {
    char ch = gc();
    for (; isspace(ch); ch = gc());
    for (; !isspace(ch); ch = gc()) *s++ = ch;
    *s = 0;
}

void read(char &c) { for (c = gc(); isspace(c); c = gc()); }

void push(const char &c) {
#if DEBUG  // 调试，可显示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
}

void write(int x) {
    bool neg = false;
    if (x < 0) {
    neg = true;
    push('-');
    }
    static int sta[40];
    int top = 0;
    do {
    sta[top++] = x % 10;
    x /= 10;
    } while (x);
    if (neg)
    while (top) push('0' - sta[--top]);
    else
    while (top) push('0' + sta[--top]);
}

void write(int x, char lastChar) { write(x), push(lastChar); }
} io;

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
const int N=4e4+5, M=1e5+5, B=620+5;
int n, m;
int val[N]; // 如题 QwQ

int fa[B], dep[B];
int tot=1, head[N], ver[M<<1], nxt[M<<1];
void add(int x, int y) {
    ver[++tot]=y;
    nxt[tot]=head[x], head[x]=tot;
}

struct Clus {
    /**
    * 这一部分代码时通过原树建立收缩树
    * 
    * 注意： 这里因为不太好处理边属于哪一个块
    *        所以大部分地方使用一条边的儿子节点代指这个边
    * 
    *        1. 链式前向星从0开始 (貌似没什么关系)
    *        2. if(!flag && !R[c]) R[c]=x; 这里一定为 &&
    *        3. 分清楚内网 fa, dep
    *        4. 块数量可能>sqrt(n) , 开成n
    *        5. 由于强制在线，RE可肯能为WA
    */

    int Block;      // 块的大小

    int tot=1, head[N], ver[M<<1], nxt[M<<1];
    void add(int x, int y) {
        ver[++tot]=y;
        nxt[tot]=head[x], head[x]=tot;
    }

    int fa[N];      // 每一个节点在原树上的父亲
    int dep[N];     // 每一个节点在原树上的深度

    int cnt;        // 块数量
    int L[B], R[B]; // 一个块的两个界点
    int tag[N];     // 每一个节点连向父亲的边属于的块 (计算过程中得到，不完整)

    void join(int x, int y, int l, int r) {
        ++cnt, L[cnt]=x, R[cnt]=y;
        for(int i=l; i!=r; i=nxt[i]) {
            int y=ver[i];
            if(y!=fa[x]) tag[y]=cnt;
        }
    }

    int siz[N]; // 在计算过程中每一个点子树中未被分配的点的数量
    int Clu[N]; // 在计算过程中每一个点子树中的最后一个界点 (最近的界点)

    // 进行块划分
    void build1(int x, int f) {
        fa[x]=f, dep[x]=dep[f]+1, siz[x]=1;
        int num=0; // 计算过程中界点个数 
        for(int i=head[x]; i; i=nxt[i]) {
            int y=ver[i];
            if(y==f) continue;
            build1(y, x);

            siz[x]+=siz[y];
            if(Clu[y]) num++, Clu[x]=Clu[y];
        }

        if(num>1 || siz[x]>=Block || x==1) { // 三选一
            Clu[x]=x, siz[x]=0;          // 这颗子树应当会被完全分配
            int sum=1, id=0, li=head[x]; // id: 最后一个界点 li: 上一个子树带界点的边
            for(int i=head[x]; i; i=nxt[i]) {
                int y=ver[i];
                if(y==fa[x]) continue;
                if(sum+siz[y]>Block || (id && Clu[y])) // 二选一
                    join(x, id, li, i), sum=id=0, li=i;
                if(Clu[y]) id=Clu[y];
                sum+=siz[y];
            }
            join(x, id, li, 0);
        }
    }

    int col[N];  // 每一个点向父亲的边的组别
    bool vis[N]; // 防止连重边
    // 创建收缩树； c 表示当前节点向父亲的边
    void build2(int x, int c) {
        col[x]=c; 
        bool flag=0; 
        for(int i=head[x]; i; i=nxt[i]) {
            int y=ver[i];
            if(y==fa[x]) continue;
            int nxtc = tag[y] ? tag[y] : c;
            build2(y, nxtc);

            flag=1;
            if(!vis[nxtc] && c!=nxtc) {
                vis[nxtc]=true; // 每一个 nxtc 只会有一个入边
                ::add(c, nxtc);
                ::add(nxtc, c);
            }
        }

        if(!flag && !R[c]) R[c]=x;
    }

    // 更新收缩树基本信息
    void build3(int x, int f) {
        ::fa[x]=f, ::dep[x]=::dep[f]+1;
        for(int i=::head[x]; i; i=::nxt[i]) {
            int y=::ver[i];
            if(y==f) continue;
            build3(y, x);
        }
    }

    void init() {
        Block=1000;

        // 建立 Cluster
        build1(1, 0);
        ++cnt, col[1]=cnt;
        L[cnt]=1, R[cnt]=1;
        build2(1, cnt), build3(cnt, 0);
    }
};
Clus T; // 不想写 namespace

struct LCA {
    vector<int> v[N];

    int dep[N];
    int fa[N][21];

    void build(int x,int f){
        dep[x]=dep[f]+1;
        fa[x][0]=f;
        for(int i=1;i<=20;i++)
            fa[x][i]=fa[fa[x][i-1]][i-1];
        for(auto y: v[x]){
            if(y==f) continue;
            build(y,x);
        }
    }

    int lca(int x,int y){
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=20;i>=0;i--){
            if(dep[fa[x][i]]>=dep[y])
                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];
    }
};
LCA L;


/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

vector< bitset<N> > col; // 卡常
bitset<N> dis[310][310];

// 预处理收缩树中边点的信息
void init() {
    T.init();
    col.reserve(T.cnt+1);

    // 处理每一个块 R~L 的路径信息
    for(int i=1; i<=T.cnt; i++) {
        int p=T.R[i];
        col[i].set(val[p]);
        while(p!=T.L[i]) {
            p=T.fa[p];
            col[i].set(val[p]);
        } 
    }
}

void vio_query(int x, int y, bitset<N>& ans) {
    if(T.dep[x]<T.dep[y]) swap(x, y);
    while(T.dep[x] > T.dep[y]) ans.set(val[x]), x=T.fa[x];
    while(x != y) {
        ans.set(val[x]), ans.set(val[y]);
        x=T.fa[x], y=T.fa[y];
    }
    ans.set(val[x]);
}

int query(int x, int y) {
    bitset<N> ans(0);
    int cx=T.col[x], cy=T.col[y];
    if(cx==cy) {
        vio_query(x, y, ans);
        return ans.count(); // case 1.
    }
    int lca=L.lca(x,y), cl=T.col[lca]; 
    // 这里 lca 无论是原树还是新树应当都是可以的

    if(cl==cy) { // case 2.
        swap(x,y), swap(cx,cy);
        goto case3;
    } else if (cl==cx) { // case 3.
        case3:

        int lcy=0;        // 最后一个界点
        vio_query(y, T.L[cy], ans), lcy=cy, cy=fa[cy];
        while(cy!=cl) ans|=col[cy], lcy=cy, cy=fa[cy];

        vio_query(x, T.L[lcy], ans);
        return ans.count();
    } else {
        int lcx=0, lcy=0; // 最后一个界点
        vio_query(x, T.L[cx], ans), lcx=cx, cx=fa[cx];
        vio_query(y, T.L[cy], ans), lcy=cy, cy=fa[cy];
        while(cx!=cl) ans|=col[cx], lcx=cx, cx=fa[cx];
        while(cy!=cl) ans|=col[cy], lcy=cy, cy=fa[cy];
        vio_query(T.L[lcx], T.L[lcy], ans);
        return ans.count();
    }
}

namespace LSH { // 最简单的离散化
    int a[N];

    void main() {
        for(int i=1; i<=n; i++) a[i]=val[i];
        sort(a+1, a+n+1);
        for(int i=1; i<=n; i++)
            val[i]=lower_bound(a+1, a+n+1, val[i])-a;
    }
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    io.read(n), io.read(m);
    for(int i=1; i<=n; i++) io.read(val[i]);
    for(int i=1; i<n; i++) {
        int x, y; io.read(x), io.read(y);
        L.v[x].push_back(y);
        L.v[y].push_back(x);
        T.add(x, y);
        T.add(y, x);
    }

    LSH::main();

    init();
    L.build(1, 0);

    int last_ans=0;
    while(m --> 0) {
        int x, y; io.read(x), io.read(y);
        x^=last_ans;
        io.write(last_ans=query(x, y), '\n');
    }

    return 0;
}

回滚莫队

有的时候，题目我们发现是通过莫队实现 2，但是我们发现对于增加区间可以通过 \(\mathcal O(1)\) 完成，但是对于删除就不行（比如说是某一个权值的最大值）。

为了解决这个问题，我们可以选择通过更多的添加操作去代替, 比如说我们把询问的区间进行分组，然后每一组取他们的重合区间，于是都转化为扩张了。

具体来说，先正常，进行分类讨论：

  • 当 \(l,r\) 在同一个块中，直接暴力进行计算。

  • 当 \(l\) 所在的块 \([L,R]\) 相比上一个询问发生改变，此时令 \(l = R+1, r = R\) 。

  • 当 \(l,r\) 不在一个块中：

    • 扩展右端点达到查询区间（由于保证在这一区间内，右端点单调）。

    • 扩展左端点 （由于每一次会重新回到 \(R+1\) ，而当前查询的每一个 \(l < R+1\)）。

    • 回溯左端点（这里一般是会把扩展左端点时的答案记录为 \(\texttt{Tmp}\) ，然后回溯时只需要删除其在桶中进行的操作）

示例代码 P5906 【模板】回滚莫队&不删除莫队 
  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
#include <bits/stdc++.h>
using namespace std;
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
const int N=4e5+5;
int n, m;
int c[N];

int len;
struct que {
    int l, r, id;
    bool operator < (const que& oth) const {
        if(l/len != oth.l/len) return l<oth.l;
        return r<oth.r;
    }
}a[N];
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
#define R(x) min(((((x)/len)+1)*len-1), n)

int ans[N];

namespace LSH {
    int tot, a[N];
    void main() {
        sort(a+1, a+tot+1);
        tot=unique(a+1, a+tot+1)-a-1;
        for(int i=1; i<=n; i++) {
            c[i]=lower_bound(a+1, a+tot+1, c[i])-a;
        }
    }
}

int pos[N];
int st[N], ed[N];
/*~~~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~~~*/
signed main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>c[i];
        LSH::a[++LSH::tot]=c[i];
    }

    LSH::main();

    cin>>m;
    for(int i=1; i<=m; i++) {
        int l, r; cin>>l>>r;
        a[i]=que{l, r, i};
    }

    len=ceil(sqrt(n));
    sort(a+1, a+m+1);

    int Last_Block=-1, Ans=0;

    for(int i=1, l=0, r=0; i<=m; i++) {
        if(a[i].l/len == a[i].r/len) {
            for(int j=a[i].l; j<=a[i].r; j++) {
                if(!pos[c[j]]) pos[c[j]]=j;
                ans[a[i].id]=max(ans[a[i].id], j-pos[c[j]]);
            }
            for(int j=a[i].l; j<=a[i].r; j++)
                pos[c[j]]=0;
            continue;
        }

        if(a[i].l/len != Last_Block) {
            for(int j=l; j<=r; j++)
                st[c[j]]=ed[c[j]]=0;
            r=R(a[i].l), l=r+1;
            Ans=0;
        }

        while(r<a[i].r) {
            ++r, ed[c[r]]=r;
            if(!st[c[r]]) st[c[r]]=r;

            Ans=max(Ans, r-st[c[r]]);
        }

        int Tmp=Ans, L=l;
        while(l>a[i].l) {
            l--;
            if(!ed[c[l]]) ed[c[l]]=l;
            Tmp=max(Tmp, ed[c[l]]-l);
        }

        ans[a[i].id]=Tmp;

        while(l<L) {
            if(ed[c[l]]==l) ed[c[l]]=0;
            l++;
        }

        Last_Block=a[i].l/len;
    }

    for(int i=1; i<=m; i++) cout<<ans[i]<<'\n';

    return 0;
}

注意

有些一些简单的最大最小值问题实际上是可以使用普通莫队做的：

比如说要维护一个区间中出现最多次的数字出现的个数（参见 P1997 faebdc 的烦恼）。

这个时候我们可以使用以下办法解决：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int sum, cnt[N], t[N];
void add(int x) { 
    t[cnt[x]]--;
    t[++cnt[x]]++;
    sum=max(sum, cnt[x]);
}
void del(int x) { 
    t[cnt[x]]--;
    if(sum==cnt[x] && !t[cnt[x]])
        sum--;
    t[--cnt[x]]++;
}

对于维护莫队的数据结构的选择

由于在莫队中插入一共有 \(N \sqrt Q\) 次， 但是查询只有 \(Q\) 次。

所以此时如果我们选择一个修改 \(\mathcal O(1)\) ，查询 \(\mathcal O(\sqrt N)\) 的数据结构（即分块），此时时间复杂度就会被平衡为 \(\mathcal O( N \sqrt Q + Q \sqrt N)\) 。而如果写线段树等看似更快的数据结构，此时时间复杂度为 \(\mathcal O(N \sqrt Q \log N + Q \log N)\) 反而更劣。

在最后

下面是我写的时候常见的错误：

  • 排序的第一个 != 写成 == 。

  • 把 l, r 和 a[i].l， a[i].r 搞反。

  1. 来自 OI-WIKI。 ↩

  2. 可能是看题目标签 ↩