强推这首原创曲！封面是曲绘！https://www.youtube.com/watch?v=ZpwBncHdUXE

大きな空に 向かって~ 大きな声で 歌うよ~

分治先放放，学点实用性更强的小玩意。🫡

概述

莫队是一种处理区间询问的离线算法，由莫涛对其进行了详细的归纳总结，因而得名。经过选手们对莫队算法的改造，莫队有了多种扩展版本，可以处理树上问题、带修问题等，功能十分强大。

不同莫队的适用问题类型不同，下面一一进行讲述。

分类

普通莫队

最先提出的莫队算法，用来处理静态区间询问问题。

我们把所有查询全部离线存储，维护一个滑动窗口 $[l,r]$ ，每次询问将窗口的左右边界移动到询问的左右边界，移动的同时需要更新窗口内维护的相关信息，这样一旦将滑动窗口移到询问的左右界，我们就可以使用维护好的信息快速得到询问的答案。

形式化描述，我们每次在四个方向上对窗口 $[l,r]$ 进行移动：

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

可以看到本质上就是区间在不断伸缩。

显而易见，询问的排列顺序会极大的影响算法整体的运行效率。对于不好的顺序，算法会退化到 $O(n^2)$ 。我们借助类似分块算法的平衡复杂度思想，先将整个序列按照块长 $O(\sqrt{n})$ 分块，使用复杂度均摊的喵喵分析，按照特定的排序策略，可以把时间复杂度优化到 $O(n\sqrt{n})$ 。常见的询问排序策略如下：

经典排序：询问左边界的块号作为第一关键字升序排序，询问右边界作为第二关键字升序排序。

奇偶优化排序：询问左边界的块号作为第一关键字升序排序，对于奇数块号，询问右边界作为第二关键字升序排序，对于偶数块号，询问右边界作为第二关键字降序排序。

奇偶优化后整体效率可以提升30%左右。

后来又多了一种奇妙的排序策略，名为希尔伯特排序，参见这篇CF博客：https://codeforces.com/blog/entry/61203

大体思路是把左右边界放到希尔伯特曲线的两个维度上作为坐标，按照这个顺序进行排序。这种排序策略又比奇偶排序快，而且 $n$ 和 $q$ 的比值越大，优化效率越明显。（缺点就是太难写）

SP3267 DQUERY - D-query

P2709 小B的询问

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

P3709 大爷的字符串题

P4462 [CQOI2018] 异或序列

带修莫队

有时题目会带有修改操作，此时普通莫队算法难以处理，需要引入带修莫队。

带修莫队在普通莫队的基础上加入了时间维度，每次在六个方向上对窗口 $[l,r,t]$ 进行移动：

  • $[l-1,r,t]$
  • $[l+1,r,t]$
  • $[l,r-1,t]$
  • $[l,r+1,t]$
  • $[l,r,t-1]$
  • $[l,r,t+1]$

时间对应的维度只有一个 $t$ 变量，因为带修本质上考虑的是时间序列上的某个前缀的状态，一个变量就能描述。在这个意义上，$t$ 变量和 $r$ 的移动逻辑一样，都是窗口的右指针。

由于加入了一个新维度，分块策略、排序策略也需要相应修改。我们取块长 $O(n^{\frac{2}{3}})$ 进行分块，排序策略如下：

询问左边界所在块号作为第一关键字升序排序，右边界所在块号作为第二关键字升序排序，时间作为第三关键字升序排序。

按照这样的策略进行排序，在 $n$ 、$m$ 、$t$ 同阶的情况下，时间复杂度可以做到 $O(n^{\frac{5}{3}})$ 。证明暂略。

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

单点修改，查询区间颜色数。

典中典题，有多种做法，除了带修莫队当然也可以转三维数点，使用CDQ分治。

类似小Z的袜子和HH的项链，维护颜色词频的时候更新颜色数即可。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e6 + 10;
constexpr int MOD = 998244353;

struct {
    int l, r, t, id;
} q[N];
array<int, 2> up[N];
int a[N], ans[N], bi[N];
int cnt[N];
int n, m, cntq, tim;
int res;

void add(int v) {
    cnt[v]++;
    if (cnt[v] == 1) res++;
}

void del(int v) {
    cnt[v]--;
    if (cnt[v] == 0) res--;
}

void updateTime(int l, int r, int t) {
    auto& [pos, v] = up[t];
    if (l <= pos && pos <= r) {
        del(a[pos]);
        add(v);
    }
    swap(a[pos], v);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'Q') {
            ++cntq;
            q[cntq] = {x, y, tim, cntq};
        } else {
            ++tim;
            up[tim] = {x, y};
        }
    }
    int blen = max<int>(1, pow(n, 2.0 / 3));
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    sort(q + 1, q + cntq + 1, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        if (bi[x.r] != bi[y.r]) return bi[x.r] < bi[y.r];
        return x.t < y.t;
    });
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cntq; ++i) {
        auto [ql, qr, qt, id] = q[i];
        while (l > ql) add(a[--l]);
        while (r < qr) add(a[++r]);
        while (l < ql) del(a[l++]);
        while (r > qr) del(a[r--]);
        while (t < qt) updateTime(l, r, ++t);
        while (t > qt) updateTime(l, r, t--);
        ans[id] = res;
    }
    for (int i = 1; i <= cntq; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

SP30906 ADAUNIQ - Ada and Unique Vegetable

CF940F Machine Learning

单点修改，查询区间每个数字出现次数的mex。

问的东西比较特殊，是出现次数的mex不是数字mex。维护每个数字 $i$ 的词频 $cnt1[i]$ 和出现次数为 $i$ 的数的个数 $cnt2[i]$ ，容易发现出现次数的mex上界在 $O(\sqrt{n})$ 的级别，每次可以直接暴力计算答案。总复杂度 $O(n^{\frac{5}{3}})$ 。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int l, r, t, id;
} q[N];
int a[N], pos[N], val[N], t[N];
int cnt1[N], cnt2[N];
int bi[N];
int ans[N];
array<int, 2> up[N];
int n, m, s, cntq;

void add(int v) {
    cnt2[cnt1[v]]--;
    cnt1[v]++;
    cnt2[cnt1[v]]++;
}

void del(int v) {
    cnt2[cnt1[v]]--;
    cnt1[v]--;
    cnt2[cnt1[v]]++;
}

void update(int l, int r, int t) {
    auto& [pos, v] = up[t];
    if (l <= pos && pos <= r) {
        del(a[pos]);
        add(v);
    }
    swap(a[pos], v);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], t[++s] = a[i];
    int u = 0;
    for (int i = 1; i <= m; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            cntq++;
            cin >> q[cntq].l >> q[cntq].r;
            q[cntq].t = u;
            q[cntq].id = cntq;
        } else {
            u++;
            cin >> up[u][0] >> up[u][1];
            t[++s] = up[u][1];
        }
    }
    int blen = max<int>(1, 2.3 * pow(n, 2.0 / 3) * pow(u, 1.0 / 3) / pow(m, 1.0 / 3));
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    sort(t + 1, t + s + 1);
    s = unique(t + 1, t + s + 1) - t - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + s + 1, a[i]) - t;
    for (int i = 1; i <= u; ++i) up[i][1] = lower_bound(t + 1, t + s + 1, up[i][1]) - t;
    sort(q + 1, q + cntq + 1, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        if (bi[x.r] != bi[y.r]) return bi[x.r] < bi[y.r];
        return x.t < y.t;
    });
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cntq; ++i) {
        auto [ql, qr, qt, id] = q[i];
        while (l > ql) add(a[--l]);
        while (r < qr) add(a[++r]);
        while (l < ql) del(a[l++]);
        while (r > qr) del(a[r--]);
        while (t < qt) update(l, r, ++t);
        while (t > qt) update(l, r, t--);
        int res = 1;
        while (res <= n && cnt2[res] > 0) res++;
        ans[id] = res;
    }
    for (int i = 1; i <= cntq; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

回滚莫队

我们做区间转移时，可能会遇到信息增加或删除不好实现（复杂度太高）的问题。如果只有增加/删除不好实现，而另一个很容易时，就可以使用回滚莫队来处理。回滚莫队的核心思想就是，既然只有一种操作好维护，那么就只维护这一种操作，另一种操作通过回滚来处理即可。

我们做区间转移时，可能会遇到信息增加或删除不好实现（复杂度太高）的问题。如果只有增加/删除不好实现，而另一个很容易时，就可以使用回滚莫队来处理。回滚莫队的核心思想就是，既然只有一种操作好维护，那么就只维护这一种操作，另一种操作通过回滚来处理即可。

回滚莫队通过若干单调指针和复杂度均摊的方法，将整个算法的复杂度控制在 $O(n\sqrt{m})$ 。

回滚莫队分为只增不删和只删不增的两种版本。

只增不删的回滚莫队

  1. 将所有查询按照左边界所在块号作为第一关键字升序，右边界作为第二关键字升序排序。
  2. 如果左右边界在相同块内，直接暴力计算答案，单次复杂度 $O(\sqrt{n})$ 。
  3. 否则，左右边界不在同一块内。每当左边界来到新块时，重置初始的滑动窗口，将窗口左边界 $l$ 移至新块右边界的右边，即 $R[b]+1$ ，将窗口右边界 $r$ 移至新块右边界，即 $R[b]$。此时窗口是空窗口。
  4. 按照左边界所在块给查询分组，可以发现同一组内右边界单调递增，因此只需要单调移动右边界 $r$ ，单组复杂度 $O(n)$ ，共 $O(\sqrt{n})$ 组，因此移动右边界总复杂度为 $O(n\sqrt{n})$ 。
  5. 调整好窗口右边界后，移动窗口左边界到查询左边界，记录答案，再将窗口左边界移回 $R[b]+1$ ，因此称之为回滚。单次复杂度 $O(\sqrt{n})$，移动左边界总复杂度 $O(m\sqrt{n})$ 。

只增不删的回滚莫队流程如上，同时我们证明了其时间复杂度为 $O(n\sqrt{n})$ ，和普通莫队相当。

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
101
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int l, r, id;
} q[N];
int a[N], t[N], bi[N], bl[N], br[N];
int ans[N], st[N], ed[N], ed2[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], t[i] = a[i];
    sort(t + 1, t + 1 + n);
    int s = unique(t + 1, t + 1 + n) - t - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + s + 1, a[i]) - t;
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= bnum; ++i) bl[i] = (i - 1) * blen + 1, br[i] = min(i * blen, n);
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    int l = 1, r = 0, last = 0;
    int ans1 = 0, tmp, _l;
    for (int i = 1; i <= m; ++i) {
        if (bi[q[i].l] == bi[q[i].r]) {
            for (int j = q[i].r; j >= q[i].l; --j) st[a[j]] = j;
            for (int j = q[i].r; j >= q[i].l; --j) chkmax(ans[q[i].id], j - st[a[j]]);
            for (int j = q[i].r; j >= q[i].l; --j) st[a[j]] = 0;
            continue;
        }
        if (bi[q[i].l] != last) {
            for (int j = l; j <= r; ++j) st[a[j]] = ed[a[j]] = 0;
            r = br[bi[q[i].l]];
            l = r + 1;
            ans1 = 0;
            last = bi[q[i].l];
        }
        while (r < q[i].r) {
            r++;
            if (!st[a[r]]) st[a[r]] = r;
            ed[a[r]] = r;
            chkmax(ans1, r - st[a[r]]);
        }
        _l = l;
        tmp = ans1;
        while (_l > q[i].l) {
            _l--;
            if (!ed2[a[_l]]) ed2[a[_l]] = _l;
            chkmax(tmp, max(ed[a[_l]], ed2[a[_l]]) - _l);
        }
        ans[q[i].id] = tmp;
        while (_l < l) {
            ed2[a[_l++]] = 0;
        }
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

AT_joisc2014_c 歴史の研究

多次询问区间内每个数与其出现次数乘积的最大值。

依旧是添加好维护，删除不好维护。继续使用回滚莫队，统计词频即可。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

struct {
    int l, r, id;
} q[N];
int a[N], t[N], ans[N];
int bi[N], br[N];
int cnt[N], cnt2[N];
int n, m, s;

void add(int v, int& ans) {
    cnt[v]++;
    chkmax(ans, t[v] * cnt[v]);
}

void del(int v) {
    cnt[v]--;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], t[i] = a[i];
    sort(t + 1, t + n + 1);
    s = unique(t + 1, t + n + 1) - t - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + s + 1, a[i]) - t;
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= bnum; ++i) br[i] = min(n, i * blen);
    sort(q + 1, q + m + 1, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    int l = 1, r = 0, last = 0;
    int ll, res, tmp;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (bi[ql] == bi[qr]) {
            for (int i = ql; i <= qr; ++i) cnt2[a[i]]++;
            for (int i = ql; i <= qr; ++i) chkmax(ans[id], t[a[i]] * cnt2[a[i]]);
            for (int i = ql; i <= qr; ++i) cnt2[a[i]] = 0;
            continue;
        }
        if (bi[ql] != last) {
            while (r > br[bi[ql]]) del(a[r--]);
            while (l < br[bi[ql]] + 1) del(a[l++]);
            res = 0;
            last = bi[ql];
        }
        while (r < qr) add(a[++r], res);
        ll = l, tmp = res;
        while (ll > ql) add(a[--ll], tmp);
        ans[id] = tmp;
        while (ll < l) del(a[ll++]);
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

只删不增的回滚莫队

  1. 首先需要将整个序列加入窗口，计算整个序列作为区间的答案值。
  2. 将所有查询按照左边界所在块号作为第一关键字升序，右边界作为第二关键字降序排序。
  3. 如果左右边界在相同块内，直接暴力计算答案，单次复杂度 $O(\sqrt{n})$ 。
  4. 否则，左右边界不在同一块内。每当左边界来到新块时，重置初始的滑动窗口，将窗口左边界 $l$ 移至新块左边界，即 $L[b]$ ，将窗口右边界 $r$ 移至序列末端，即 $n$ 。此时窗口是包含新块在内的序列后缀。
  5. 按照左边界所在块给查询分组，可以发现同一组内右边界单调递减，因此只需要单调移动右边界 $r$ ，单组复杂度 $O(n)$ ，共 $O(\sqrt{n})$ 组，因此移动右边界总复杂度为 $O(n\sqrt{n})$ 。
  6. 调整好窗口右边界后，移动窗口左边界到查询左边界，记录答案，再将窗口左边界移回 $L[b]$ ，因此称之为回滚。单次复杂度 $O(\sqrt{n})$，移动左边界总复杂度 $O(m\sqrt{n})$ 。

只删不增的回滚莫队流程如上，和第一种回滚莫队类似，其时间复杂度也为 $O(n\sqrt{n})$ 。

P4137 Rmq Problem / mex

多次询问区间内数的mex。

发现删除时统计词频即可更新，但加点则不好维护。使用只删不增的回滚莫队。细节见代码。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

struct {
    int l, r, id;
} q[N];
int a[N], ans[N], bi[N], bl[N];
int cnt[N], cnt2[N];
int n, m;

void del(int v, int& ans) {
    cnt[v]--;
    if (cnt[v] == 0) chkmin(ans, v);
}

void add(int v) {
    cnt[v]++;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= bnum; ++i) bl[i] = (i - 1) * blen + 1;
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r > y.r;
    });
    int l = 1, r = n, last = 0;
    int ll, res{}, mex{}, tmp;
    for (int i = 1; i <= n; ++i) cnt[a[i]]++;
    while (cnt[mex]) mex++;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (bi[ql] == bi[qr]) {
            for (int i = ql; i <= qr; ++i) cnt2[a[i]]++;
            while (cnt2[ans[id]]) ans[id]++;
            for (int i = ql; i <= qr; ++i) cnt2[a[i]] = 0;
            continue;
        }
        if (bi[ql] != last) {
            while (r < n) add(a[++r]);
            while (l < bl[bi[ql]]) del(a[l++], mex);
            res = mex;
            last = bi[ql];
        }
        while (r > qr) del(a[r--], res);
        ll = l, tmp = res;
        while (ll < ql) del(a[ll++], tmp);
        ans[id] = tmp;
        while (ll > l) add(a[--ll]);
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    solve();

    return 0;
}

树上莫队

此处只介绍将树拍平成括号序后在新序列上跑莫队的trick，称之为括号序树上莫队。对于真正的树上莫队，实际使用极少，一般都有复杂度更好的做法。

DFS序列、括号序列、欧拉序列的区别：

DFS序列：DFS树时按照每个节点首次访问时间生成的长度为 $n$ 的序列。

括号序列：DFS树时进入和退出某点时均记录一次，生成的长度为 $2n$ 的序列。

欧拉序列：DFS树时每访问一次节点就记录一次，生成的长度为 $2n-1$ 的序列。

和线性序列不同，树拍平成括号序后，一个点会在序列中出现两次，因此我们处理贡献时需要额外记录一个 $vis[x]$ 信息，如果未访问过则贡献，访问过则取消贡献。生成括号序时，我们记进入点 $x$ 的时间为 $f_{x}$ ，退出点 $x$ 的时间为 $g_{x}$ 。询问点 $u$ 到点 $v$ 之间的树链（这里默认点 $u$ 的访问时间早于点 $v$ ），我们需要判断 $u$ 是不是 $v$ 的祖先，如果是，则莫队处理的区间是 $[f_{u}, f_{v}]$ ；否则区间为 $[g_{u}, f_{v}]$ 再加上二者的最近公共祖先，因为根据括号序的性质，最近公共祖先这个点不在区间中，记录答案前额外计算这个点的贡献即可。

P4074 [WC2013] 糖果公园

一棵树，每个点有颜色，一种颜色出现不同次造成的贡献由权值指定，单点修改节点颜色，询问某条树链的总贡献。

按照上面的处理逻辑在括号序列上跑莫队即可。单点修改，需要使用带修莫队。

注意分块时是对括号序（长度 $2n$ ）分块，而不是对原序列分块！

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int LOG = 17;
constexpr int MOD = 998244353;

struct {
    int l, r, t, id;
} q[N];
int v[N], w[N], c[N];
array<int, 2> up[N];
vector<int> e[N];
int id[N], ans[N];
int f[N], g[N], idx;
int fa[N][LOG], d[N];
int n, m, tim, Q, cntq;
int bi[N];
int vis[N], cnt[N];
int res;

void dfs(int u) {
    id[f[u] = ++idx] = u;
    for (int v : e[u]) {
        if (v == fa[u][0]) continue;
        fa[v][0] = u;
        d[v] = d[u] + 1;
        dfs(v);
    }
    id[g[u] = ++idx] = u;
} 

int lca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i) {
        if (d[fa[u][i]] >= d[v]) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

void add(int x) {
    if (vis[x]) res -= v[c[x]] * w[cnt[c[x]]--];
    else res += v[c[x]] * w[++cnt[c[x]]];
    vis[x] ^= 1;
}

void update(int t) {
    auto& [pos, v] = up[t];
    if (vis[pos]) {
        add(pos);
        swap(c[pos], v);
        add(pos);
    } else {
        swap(c[pos], v);
    }
}

void solve() {
    read(n, m, Q);
    for (int i = 1; i <= m; ++i) read(v[i]);
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        read(u, v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) read(c[i]);
    d[1] = 1;
    dfs(1);
    for (int i = 1; i < LOG; ++i) {
        for (int u = 1; u <= n; ++u) {
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        }
    }
    while (Q--) {
        int op, x, y;
        read(op, x, y);
        if (op == 0) {
            up[++tim] = {x, y};
        } else {
            if (f[x] > f[y]) swap(x, y);
            q[++cntq] = {lca(x, y) == x ? f[x] : g[x], f[y], tim, cntq};
        }
    }
    int blen = max<int>(1, pow(2 * n, 2.0 / 3));
    for (int i = 1; i <= 2 * n; ++i) bi[i] = (i - 1) / blen + 1;
    sort(q + 1, q + cntq + 1, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        if (bi[x.r] != bi[y.r]) return bi[x.r] < bi[y.r];
        return x.t < y.t;
    });
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cntq; ++i) {
        auto [ql, qr, qt, _id] = q[i];
        while (l > ql) add(id[--l]);
        while (r < qr) add(id[++r]);
        while (l < ql) add(id[l++]);
        while (r > qr) add(id[r--]);
        while (t < qt) update(++t);
        while (t > qt) update(t--);
        int u = id[ql], v = id[qr];
        int Lca = lca(u, v);
        if (u != Lca && v != Lca) {
            add(Lca);
            ans[_id] = res;
            add(Lca);
        } else {
            ans[_id] = res;
        }
    }
    for (int i = 1; i <= cntq; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

二次离线莫队

25.9.17更 | 孩子们我打完ICPC网络赛了，学完二次离线莫队过来填坑了

有的题目里，窗口更新时无法做到单点 $O(1)$ 的转移。但是如果贡献满足可差分性（可减性、可拆性），我们可以考虑算出单次查询与前一次查询的变化量，最后做一次前缀和即可得到所有答案。

考虑窗口从 $[l,r]$ 扩张至 $[l,r+1]$ ，这个过程中增加了 $a_{r+1}$ 关于区间 $[l,r]$ 产生的贡献。我们定义 $f(x,l,r)$ 表示下标为 $x$ 的数关于区间 $[l,r]$ 产生的贡献，即扩张时增加了 $f(r+1,l,r)$ 。根据贡献的可差分性，$f(r+1,l,r)=f(r+1,1,r)-f(r+1,1,l-1)$ 。显然我们可以通过预处理来计算所有形如 $f(i+1,1,i)$ 的贡献，这就是 $a_{i+1}$ 关于序列前缀 $[1,i]$ 的贡献，使用某些数据结构即可维护。那么我们还需计算的就是后面的 $f(r+1,1,l-1)$ 。这个例子右边界只移动了一个单位距离，如果移动一段距离，即从 $[l,r]$ 扩张至 $[l,qr]$ ，那么我们需要计算的一系列贡献为 $f(x,1,l-1),x\in[r+1,qr]$ 。我们发现这些贡献都是针对 $[1,l-1]$ 的前缀的，容易想到跑完莫队后进行第二次离线，类似扫描线的方式更新贡献，再次查询。窗口右边界收缩、窗口左边界扩张和收缩同理，预处理一些前缀后缀信息，拆出一部分贡献做第二次离线。这就是所谓的“二次离线莫队”，这个二次离线和莫队一点关系都没有，你圈典中典的无力吐槽的神奇命名。

值得注意的是第二次离线过程中，询问总量是 $O(n\sqrt{n})$ 的量级，所以需要快速的查询算法，而更新共需要做 $O(n)$ 次，相对而言可以慢一些。我们往往使用分块来平衡复杂度， $O(\sqrt{n})$ 时间复杂度来修改，$O(1)$ 复杂度来查询，这样可以把整体的复杂度平衡至 $O(n\sqrt{n})$ 。

于是讲完了。二次离线莫队难点在于细节巨多，极易出错，强烈建议读者多动手。

P4887 【模板】莫队二次离线（第十四分块(前体)）

给定序列 $a$ 和整数 $k$ ，询问区间 $[l,r]$ 内满足 $l \le i \lt j \le r, popcount(a_{i} \oplus a_{j})=k$ 的二元组 $(i,j)$ 的个数。

序列的值域很小，预处理值域内所有 $popcount(v)=k$ 的数。计算所有 $f(i+1,1,i)$ 并求前缀和，计算所有 $f(i-1,i,n)$ 并求后缀和。开桶来统计，每次加入 $a_i$ 的词频后，所有满足 $popcount(v)=k$ 的 $v \oplus a_i$ 的词频都加 $1$，即可方便的维护这部分贡献。

考虑第二次离线的过程。还是使用权值数组，每个位置 $O(\binom{k}{14})$更新词频，单点 $O(1)$ 累加即可。复杂度 $O(n(\sqrt{n}+\binom{k}{14}))$ 。

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 <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 1e5 + 10;
constexpr int V = 1 << 14;
constexpr int MOD = 998244353;

int a[N], cnt[V], bi[N];
vector<tuple<int, int, int, int>> e1[N], e2[N];
i64 pre[N], suf[N], ans[N];
int b[V], cntb;
struct {
    int l, r, id;
} q[N];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    for (int i = 0; i < V; ++i) {
        if (__builtin_popcount(i) == k) b[++cntb] = i;
    }
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + cnt[a[i]];
        for (int j = 1; j <= cntb; ++j) {
            cnt[b[j] ^ a[i]]++;
        }
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = n; i >= 1; --i) {
        suf[i] = suf[i + 1] + cnt[a[i]];
        for (int j = 1; j <= cntb; ++j) {
            cnt[b[j] ^ a[i]]++;
        }
    }
    int blen = sqrt(n);
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (qr > r) {
            ans[id] += pre[qr] - pre[r];
            e1[l - 1].emplace_back(r + 1, qr, id, -1);
        } else if (qr < r) {
            ans[id] -= pre[r] - pre[qr];
            e1[l - 1].emplace_back(qr + 1, r, id, 1);
        }
        r = qr;
        if (ql < l) {
            ans[id] += suf[ql] - suf[l];
            e2[r + 1].emplace_back(ql, l - 1, id, -1);
        } else if (ql > l) {
            ans[id] -= suf[l] - suf[ql];
            e2[r + 1].emplace_back(l, ql - 1, id, 1);
        }
        l = ql;
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= cntb; ++j) {
            cnt[b[j] ^ a[i]]++;
        }
        for (auto [l, r, id, op] : e1[i]) {
            for (int j = l; j <= r; ++j) {
                ans[id] += 1LL * op * cnt[a[j]];
            }
        }
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= cntb; ++j) {
            cnt[b[j] ^ a[i]]++;
        }
        for (auto [l, r, id, op] : e2[i]) {
            for (int j = l; j <= r; ++j) {
                ans[id] += 1LL * op * cnt[a[j]];
            }
        }
    }
    for (int i = 2; i <= m; ++i) ans[q[i].id] += ans[q[i - 1].id];
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

给定序列 $a$ ，询问区间 $[l,r]$ 内的逆序对数。

数据结构痴必吃榜。我们已经有了 $O(n\sqrt{m})$ 时间，$O(n\sqrt{m})$ 空间的在线做法，使用二次离线莫队可以做到 $O(n\sqrt{m})$ 时间，$O(n+m)$ 空间。

预处理的前缀后缀信息可以简单的使用树状数组维护。重点在于二次离线，询问次数是 $O(n\sqrt{m})$ 的，需要使用修改 $O(\sqrt{n})$ ，查询 $O(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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

int a[N], bi[N], bl[N], br[N], t[N], s;
i64 pre[N], suf[N];
int cnt1[N], cnt2[N];
int tree[N];
int n, m;
i64 ans[N]; 
vector<tuple<int, int, int, int>> e1[N], e2[N];
struct {
    int l, r, id;
} q[N];


void add(int x, int v) {
    while (x <= s) {
        tree[x] += v;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += tree[x];
        x -= x & -x;
    }
    return res;
}

void modify1(int v) {
    for (int i = 1; i < bi[v]; ++i) cnt1[i]++;
    for (int i = bl[bi[v]]; i < v; ++i) cnt2[i]++;
}

void modify2(int v) {
    for (int i = bi[v] + 1; i <= bi[s]; ++i) cnt1[i]++;
    for (int i = br[bi[v]]; i > v; --i) cnt2[i]++;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], t[i] = a[i];
    sort(t + 1, t + 1 + n);
    s = unique(t + 1, t + 1 + n) - t - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(t + 1, t + s + 1, a[i]) - t;
    int blen = sqrt(n);
    int bnum = (n + blen - 1) / blen;
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(i * blen, n);
    }
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + query(s) - query(a[i]);
        add(a[i], 1);
    }
    memset(tree, 0, sizeof tree);
    for (int i = n; i >= 1; --i) {
        suf[i] = suf[i + 1] + query(a[i] - 1);
        add(a[i], 1);
    }
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (qr > r) {
            ans[id] += pre[qr] - pre[r];
            e1[l - 1].emplace_back(r + 1, qr, id, -1);
        } else if (qr < r) {
            ans[id] -= pre[r] - pre[qr];
            e1[l - 1].emplace_back(qr + 1, r, id, 1);
        }
        r = qr;
        if (ql < l) {
            ans[id] += suf[ql] - suf[l];
            e2[r + 1].emplace_back(ql, l - 1, id, -1);
        } else if (ql > l) {
            ans[id] -= suf[l] - suf[ql];
            e2[r + 1].emplace_back(l, ql - 1, id, 1);
        }
        l = ql;
    }
    for (int i = 1; i <= n; ++i) {
        modify1(a[i]);
        for (auto [l, r, id, op] : e1[i]) {
            for (int j = l; j <= r; ++j) {
                ans[id] += op * (cnt1[bi[a[j]]] + cnt2[a[j]]);
            }
        }
    }
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    for (int i = n; i >= 1; --i) {
        modify2(a[i]);
        for (auto [l, r, id, op] : e2[i]) {
            for (int j = l; j <= r; ++j) {
                ans[id] += op * (cnt1[bi[a[j]]] + cnt2[a[j]]);
            }
        }
    }
    for (int i = 2; i <= m; ++i) ans[q[i].id] += ans[q[i - 1].id];
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5501 [LnOI2019] 来者不拒，去者不追

给定序列 $a$ ，询问区间 $[l,r]$ 内所有数的权值和。如果 $a_i$ 在区间内是第 $k$ 小，其权值为 $k\times a_i$ 。

拆贡献，发现加入$a_i$ 时，答案增加值为 $(区间内比a_i小的数的数量+1)\times a_i+区间内比a_i大的数之和$ 。贡献中的 $+1$ 的系数导致计算前缀和会重复计算，把这部分贡献拆出来最后统一补偿，只计算 $区间内比a_i小的数的数量\times a_i+区间内比a_i大的数之和$ 。预处理维护两棵权值树状数组，二次离线时使用值域分块即可。

值得注意的是这个贡献的性质比较好，我们可以把左右边界扩张和收缩统一使用前缀和和同一种二次离线来处理，代码量会小很多。

时间复杂度依旧是 $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
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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

i64 treeCnt[N], treeSum[N];
int a[N];
i64 pre[N], ans[N];
i64 preSum[N];
vector<tuple<int, int, int, int>> e[N];
struct {
    int l, r, id;
} q[N];
int bi[N], bl[N], br[N];
int cnt1[N], cnt2[N];
i64 sum1[N], sum2[N];
int n, m, mx;

void add(i64* t, int x, int v) {
    while (x <= mx) {
        t[x] += v;
        x += x & -x;
    }
}

i64 query(i64* t, int x) {
    i64 res = 0;
    while (x) {
        res += t[x];
        x -= x & -x;
    }
    return res;
}

void modifyLessCnt(int v) {
    for (int i = bi[v] + 1; i <= bi[mx]; ++i) cnt1[i]++;
    for (int i = v + 1; i <= br[bi[v]]; ++i) cnt2[i]++;
}

void modifyMoreSum(int v) {
    for (int i = 1; i < bi[v]; ++i) sum1[i] += v;
    for (int i = bl[bi[v]]; i < v; ++i) sum2[i] += v;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], chkmax(mx, a[i]);
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        cin >> l >> r;
        id = i;
    }
    for (int i = 1; i <= n; ++i) preSum[i] = preSum[i - 1] + a[i];
    int blen = sqrt(N), bnum = (N + blen - 1) / blen;
    for (int i = 1; i < N; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= bnum; ++i) {
        bl[i] = (i - 1) * blen + 1;
        br[i] = min(N, i * blen);
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + query(treeCnt, a[i] - 1) * a[i] + query(treeSum, mx) - query(treeSum, a[i]);
        add(treeCnt, a[i], 1);
        add(treeSum, a[i], a[i]);
    }
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (qr > r) {
            ans[id] += pre[qr] - pre[r];
            e[l - 1].emplace_back(r + 1, qr, id, -1);
        } else if (qr < r) {
            ans[id] -= pre[r] - pre[qr];
            e[l - 1].emplace_back(qr + 1, r, id, 1);
        }
        r = qr;
        if (ql < l) {
            ans[id] -= pre[l - 1] - pre[ql - 1];
            e[r].emplace_back(ql, l - 1, id, 1);
        } else if (ql > l) {
            ans[id] += pre[ql - 1] - pre[l - 1];
            e[r].emplace_back(l, ql - 1, id, -1);
        }
        l = ql;
    }
    for (int i = 1; i <= n; ++i) {
        modifyLessCnt(a[i]);
        modifyMoreSum(a[i]);
        for (auto [l, r, id, op] : e[i]) {
            for (int j = l; j <= r; ++j) 
                ans[id] += op * (1LL * a[j] * (cnt1[bi[a[j]]] + cnt2[a[j]]) + sum1[bi[a[j]]] + sum2[a[j]]);
        }
    }
    for (int i = 2; i <= m; ++i) ans[q[i].id] += ans[q[i - 1].id];
    for (int i = 1; i <= m; ++i) ans[q[i].id] += preSum[q[i].r] - preSum[q[i].l - 1];
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

P5398 [Ynoi2018] GOSICK

给定序列 $a$ ，询问区间 $[l,r]$ 内满足 $l \le i,j \le r$ 且 $a_i$ 是 $a_j$ 倍数的二元组 $(i,j)$ 的个数。

这里 $(i,i)$ 二元组只计算一次，而 $(i,j)$ 和 $(j,i)$ 被看作两个二元组，贡献两次。由于贡献的逻辑不同，我们暂不考虑 $(i,i)$ 的贡献，把这部分答案放到最后统一补偿。

显然新加入 $a_i$ 后，其新增贡献为整个区间中 $a_i$ 的因数和倍数个数。试除法分解因数是 $O(\sqrt{V})$ 的，前缀信息可以在 $O(n\sqrt{V})$ 的时间内预处理。考虑第二次离线的过程，对于 $a_i$ ，我们更新其因数的词频，同时若 $a_i$ 大于 $O(\sqrt{V})$ ，则更新其倍数的词频。这里是根号分治，保证整体的复杂度正确。第二次离线做完之后，还有小于等于 $O(\sqrt{V})$ 的 $a_i$ 作为因数的贡献没有处理。我们再做第三次离线，处理前缀等于 $v$ 的数量和前缀为 $v$ 的倍数的数量，对于每个查询，$v$ 作为因数的贡献就是前缀等于 $v$ 的数量乘区间内 $v$ 的倍数的数量。

同样地，可以把前缀后缀统一成前缀来进行处理。注意窗口左边界移动时的贡献，$f(l-1,l,r)=f(l-1,1,r)-f(l-1,1,l-1)$ ，对于本题，$f(x,x,x)$ 的结果是 $2$ （自己作为自己的倍数和自己的因数贡献两次），所以还需单独减掉这部分多余的贡献，即 $f(l-1,l,r)=f(l-1,1,r)-f(l-1,1,l-2)-2$ 。

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
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int LIMIT = 100;
constexpr int MOD = 998244353;

struct {
    int l, r, id;
} q[N];
u32 a[N], xcnt[N], vcnt[N], bi[N];
int headq[N], nextq[N << 1], qx[N << 1], ql[N << 1], qr[N << 1], qop[N << 1], qid[N << 1];
int cntq;
vector<int> f[N];
i64 pre[N], ans[N];
int n, m;

void add(int x, int l, int r, int id, int op) {
    nextq[++cntq] = headq[x];
    headq[x] = cntq;
    qx[cntq] = x;
    ql[cntq] = l;
    qr[cntq] = r;
    qid[cntq] = id;
    qop[cntq] = op;
}

void solve() {
    read(n, m);
    u32 blen = sqrt(n), mx = 0;
    for (int i = 1; i <= n; ++i) read(a[i]), chkmax(mx, a[i]);
    for (int i = 1; i <= n; ++i) bi[i] = (i - 1) / blen + 1;
    for (int i = 1; i <= m; ++i) {
        auto& [l, r, id] = q[i];
        read(l, r);
        id = i;
    }
    sort(q + 1, q + 1 + m, [&](auto x, auto y) {
        if (bi[x.l] != bi[y.l]) return bi[x.l] < bi[y.l];
        return x.r < y.r;
    });
    for (int i = 1; i <= n; ++i) {
        if (f[a[i]].empty()) {
            for (int j = 1; 1LL * j * j <= a[i]; ++j) {
                if (a[i] % j) continue;
                f[a[i]].push_back(j);
            }
        }
        pre[i] = pre[i - 1];
        pre[i] += xcnt[a[i]];
        for (int v2; int v : f[a[i]]) {
            v2 = a[i] / v;
            pre[i] += vcnt[v];
            xcnt[v]++;
            if (v2 != v) {
                pre[i] += vcnt[v2];
                xcnt[v2]++;
            }
        }
        vcnt[a[i]]++;
    }
    // 第一次离线 莫队
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        auto [ql, qr, id] = q[i];
        if (qr > r) {
            ans[id] += pre[qr] - pre[r];
            add(l - 1, r + 1, qr, id, -1);
        } else if (qr < r) {
            ans[id] -= pre[r] - pre[qr];
            add(l - 1, qr + 1, r, id, 1);
        }
        r = qr;
        if (ql < l) {
            ans[id] -= pre[l - 1] - pre[ql - 1] + 2 * (l - ql);
            add(r, ql, l - 1, id, 1);
        } else if (ql > l) {
            ans[id] += pre[ql - 1] - pre[l - 1] + 2 * (ql - l);
            add(r, l, ql - 1, id, -1);
        }
        l = ql;
    }
    // 第二次离线 处理部分贡献 根号分治
    memset(xcnt, 0, sizeof xcnt);
    for (int i = 1; i <= n; ++i) {
        for (int v : f[a[i]]) {
            int v2 = a[i] / v;
            xcnt[v]++;
            if (v2 != v) xcnt[v2]++;
        }
        if (a[i] > LIMIT) {
            for (int k = a[i]; k <= mx; k += a[i]) {
                xcnt[k]++;
            }
        }
        for (int j = headq[i]; j; j = nextq[j]) {
            int l = ql[j], r = qr[j], id = qid[j], op = qop[j];
            for (int k = l; k <= r; ++k) {
                ans[id] += 1LL * op * xcnt[a[k]];
            }
        }
    }
    // 第三次离线 计算剩余贡献
    for (u32 i = 1; i <= LIMIT; ++i) {
        vcnt[0] = xcnt[0] = 0;
        for (int j = 1; j <= n; ++j) {
            vcnt[j] = vcnt[j - 1] + (a[j] == i);
            xcnt[j] = xcnt[j - 1] + (a[j] % i == 0);
        }
        for (int j = 1; j <= cntq; ++j) {
            int x = qx[j], l = ql[j], r = qr[j], id = qid[j], op = qop[j];
            ans[id] += 1LL * op * vcnt[x] * (xcnt[r] - xcnt[l - 1]);
        }
    }
    for (int i = 2; i <= m; ++i) ans[q[i].id] += ans[q[i - 1].id];
    for (int i = 1; i <= m; ++i) ans[q[i].id] += q[i].r - q[i].l + 1;
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

结语

分块、莫队、根号分治，三者同样作为根号算法，有着极强的联系。它们的复杂度虽然没有对数那么优秀，但是相对地，其功能会更加强大。作为进阶必备知识点，定是数据结构痴不得不品的一环（