根号算法

2025-10-12T18:53:03+08:00 | 19 分钟阅读 | 更新于 2025-10-12T18:53:03+08:00 | 0 次阅读

@ Jason Chan

优雅的，无脑的！

1. 分块

分块不能算是一种算法，而是一种思想。

具体而言就是将一段序列分成多个块，查询时可以对块而非单点进行查询，可以大大加快时间效率。对于非整块元素，直接暴力地计算或者拆解。设块长为 $B$，那么就有 $\dfrac nB$ 块。查询或修改是块长与块数之和，即 $B+\dfrac nB\ge 2\sqrt n$，当 $B=\sqrt n$ 时取等。因此通常取 $B=\sqrt n$。

下文中，令 $L,R$ 表示一段区间内最左与最右的整块编号，以 $st_L$ 表示块的起始位置，$ed_L$ 表示块的末位置。

1.1 序列分块入门

1.1.1 基础题

P13977 数列分块入门 2

给出长度为 $n\le 2\times 10^5$ 的序列，$n$ 个操作，涉及区间加法，询问区间 $<x$ 的数个数。

首先，对于非块内元素，直接暴力算即可。对于块内元素，考虑如何维护。

如果类似前缀和的方式，由于值域很大，不能这样做。考虑二分，只要中间段有序，那么就可以二分求出答案，复杂度为 $\mathcal O(\dfrac nB\log B)$。对每个块进行预处理出有序块，这部分复杂度为 $\mathcal O(\dfrac nBB\log B)=\mathcal O(n\log B)$。

再考虑区间加对这个操作的影响。显然，区间加只会影响到最左与最右的两个非整块，特殊处理即可。这部分的复杂度是 $\mathcal O(B\log B)$。

 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


void add (int l, int r, ll c) {
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; i ++) a[i] += c;
        for (int i = st[pos[l]]; i <= ed[pos[l]]; i ++) b[i] = a[i];
        sort (b + st[pos[l]], b + ed[pos[l]] + 1);
        return;
    }
    int L = pos[l] + 1, R = pos[r] - 1;
    if (L <= R) for (int i = L; i <= R; i ++) lazy[i] += c;
    for (int i = l; i <= ed[pos[l]]; i ++) a[i] += c;
    for (int i = st[pos[r]]; i <= r; i ++) a[i] += c;
    for (int i = st[pos[l]]; i <= ed[pos[l]]; i ++) b[i] = a[i];
    for (int i = st[pos[r]]; i <= ed[pos[r]]; i ++) b[i] = a[i];
    sort (b + st[pos[l]], b + ed[pos[l]] + 1);
    sort (b + st[pos[r]], b + ed[pos[r]] + 1);
}

int query (int l, int r, ll c) {
    int cnt = 0, L = pos[l] + 1, R = pos[r] - 1;
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; i ++) cnt += (a[i] < c - lazy[pos[l]]);
        return cnt;
    }
    if (L <= R) for (int i = L; i <= R; i ++) cnt += lower_bound (b + st[i], b + ed[i] + 1, c - lazy[i]) - (b + st[i]);
    for (int i = l; i <= ed[pos[l]]; i ++) cnt += (a[i] < c - lazy[pos[l]]);
    for (int i = st[pos[r]]; i <= r; i ++) cnt += (a[i] < c - lazy[pos[r]]);
    return cnt;
}

P13978 数列分块入门 3

给出长度为 $n\le 2\times 10^5$ 的序列，$n$ 个操作，涉及区间加法，询问区间最大的 $<x$ 的数。

与上一题类似，维护有序块，然后二分查找比较即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


ll query (int l, int r, ll c) {
    ll ret = -inf, L = pos[l] + 1, R = pos[r] - 1; // -inf is important
    if (pos[l] == pos[r]) {
        for (int i = l; i <= r; i ++) if (a[i] + lazy[pos[l]] < c) ret = max (a[i] + lazy[pos[l]], ret);
        return ret == -inf ? -1 : ret;
    }
    if (L <= R) for (int i = L; i <= R; i ++) {
        int p = lower_bound (b + st[i], b + ed[i] + 1, c - lazy[i]) - b;
        if (p == st[i]) continue;
        ret = max (ret, b[p - 1] + lazy[i]);
    }
    for (int i = l; i <= ed[pos[l]]; i ++) if (a[i] + lazy[pos[l]] < c) ret = max (a[i] + lazy[pos[l]], ret);
    for (int i = st[pos[r]]; i <= r; i ++) if (a[i] + lazy[pos[r]] < c) ret = max (a[i] + lazy[pos[r]], ret);
    return ret == -inf ? -1 : ret;
}

P13980 数列分块入门 5

给出长度为 $n\le 3\times 10^5$ 的序列，$n$ 个操作，涉及区间开方，区间求和。

注意到每个数最多被开方 $\log \log a_i$ 次，因此维护区间最大值。对于开方操作，块内最大值为 $1$ 直接跳过，反之暴力开方，并更改块内和。

P13981 数列分块入门 6

给出长度为 $n\le 3\times 10^5$ 的序列，$n$ 个操作，涉及单点插入，单点查询。数据随机。

由于数据是随机的，所以每个块期望被插入 $\mathcal O(\sqrt n)$ 个元素。这样块长不会增长太吓人，做就行了。

不随机怎么做？考虑重构分块，当一个块被插入超过 $\mathcal O(\sqrt n)$ 个节点后，直接暴力重构，暴力重构的复杂度是 $\mathcal O(n)$，最多被重构 $\mathcal O(\sqrt n)$ 次，所以这个复杂度也是对的。

P13984 数列分块入门 9

给出长度为 $n\le 3\times 10^5$ 的静态序列，$n$ 次查询，每次查询区间最小众数。

这一看不好维护啊！先离散化吧！

考虑预处理 任意两个块之间（包含）的最小众数 $w_{L,R}$，对于每个块求出每个数出现的次数，并对这个东西做前缀和。

对于一次查询 $[l,r]$，可以断言：最小众数一定出现在 $w_{L,R}$ 以及 $a_i\text{ for }i\in[l,st_L)\cup(ed_R,r]$ 之中，至多是 $\mathcal O(\sqrt n)$ 个数。分别维护这些数的出现次数，用前缀和做，每次查询就是 $\mathcal O(\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


void prework () {
    tot = (n + B - 1) / B;
    for (int i = 1; i <= tot; i ++) {
        st[i] = ed[i - 1] + 1; ed[i] = min (n, st[i] + B - 1);
        for (int j = st[i]; j <= ed[i]; j ++) {
            pos[j] = i;
        }
    }

    for (int i = 1; i <= tot; i ++) {
        for (int j = st[i]; j <= ed[i]; j ++) cnt[i][a[j]] ++;
        for (int j = 1; j <= l; j ++) cnt[i][j] += cnt[i - 1][j];
    }

    for (int i = 1; i <= tot; i ++) {
        for (int j = i; j <= tot; j ++) {
            num[i][j] = num[i][j - 1];
            for (int k = st[j]; k <= ed[j]; k ++)
                if (cnt[j][a[k]] - cnt[i - 1][a[k]] > cnt[j][num[i][j]] - cnt[i - 1][num[i][j]] ||
                    (cnt[j][a[k]] - cnt[i - 1][a[k]] == cnt[j][num[i][j]] - cnt[i - 1][num[i][j]] && num[i][j] > a[k]))
                    num[i][j] = a[k];
        }
    }
}

int dududu[N];

int qury (int l, int r) {
    if (pos[l] == pos[r]) {
        int ans = 0;
        for (int i = l; i <= r; i ++) {
            ++ dududu[a[i]];
            if (dududu[a[i]] > dududu[ans] || dududu[a[i]] == dududu[ans] && a[i] < ans) ans = a[i];
        }
        for (int i = l; i <= r; i ++) dududu[a[i]] = 0;
        return ans;
    }

    int L = pos[l] + 1, R = pos[r] - 1;
    int ans = 0;
    if (L <= R) {
        ans = num[L][R];
        dududu[num[L][R]] = cnt[R][num[L][R]] - cnt[L - 1][num[L][R]];
        for (int i = l; i <= ed[pos[l]]; i ++) dududu[a[i]] = cnt[R][a[i]] - cnt[L - 1][a[i]];
        for (int i = r; i >= st[pos[r]]; i --) dududu[a[i]] = cnt[R][a[i]] - cnt[L - 1][a[i]];
    }
    for (int i = l; i <= ed[pos[l]]; i ++) {
        ++ dududu[a[i]];
        if (dududu[a[i]] > dududu[ans] || dududu[a[i]] == dududu[ans] && a[i] < ans) ans = a[i];
    }
    for (int i = r; i >= st[pos[r]]; i --) {
        ++ dududu[a[i]];
        if (dududu[a[i]] > dududu[ans] || dududu[a[i]] == dududu[ans] && a[i] < ans) ans = a[i];
    }
    for (int i = l; i <= ed[pos[l]]; i ++) dududu[a[i]] = 0;
    for (int i = r; i >= st[pos[r]]; i --) dududu[a[i]] = 0;
    dududu[num[L][R]] = 0;
    return ans;
}

1.1.2 第二分块

P4117 [Ynoi2018] 五彩斑斓的世界

给出有 $n\le10^6$ 个元素的序列 $a_i\le 10^5+1$，有两种操作：

1 l r x：将 $[l,r]$ 内大于 $x$ 的数减去 $x$。

2 l r x：查询 $[l,r]$ 内 $x$ 出现次数。

每次操作过后，序列中的数只会减小，不会变大。考虑从值域做这道题。

对于第一个操作，散块直接暴力，考虑整块怎么做。

假设当前整块的最大值为 $mx$，对 $mx$ 进行分类讨论：

$mx\le x$，无需操作。
$x<mx\le 2x$，即进行操作后最大值小于 $x$，此时暴力减。
$2x<mx$，即操作后仍然存在最大值大于 $x$。不妨对所有 $\le x$ 的元素进行 $+x$ 操作，再打上全局减 $x$ 的懒标记。

后两种情况，实际上在不断地缩小值域范围，使最大值与最小值越来越接近。这种做法类似启发式合并的思想，基于数值大小减少了维护的时间开销。

维护一个桶，暴力减相当于在 $\mathcal O(mx-x)\le \mathcal O(x)$ 的时间内将 $mx$ 减少了 $x$，最后一个操作相当于在 $\mathcal O(x)$ 的时间内将 $mx$ 减少了 $x$。也就是说，$mx$ 减少的复杂度是线性的（这就是要对减操作进行分类的目的），即每个块操作的最多只有 $\mathcal O(V)$ 次。总的操作复杂度就是 $\mathcal O(V\sqrt n)$。

对于查询操作，直接查对应位置的值即可。但是散块怎么做？

桶只能处理整块信息，难以处理散块。因此考虑值域并查集，用并查集维护每个位置的实际价值。修改操作相当于 $(i,i-x)$ 或者 $(i,i+x)$ 连边，并维护集合大小。整块的查询就是查询对应点的集合大小，散块则是对于每个位置 $find(a_i)$ 来找映射到的值，计数即可。并查集均摊下来是 $\mathcal O(1)$ 的，因此总复杂度就是 $\mathcal O(V\sqrt n+m\sqrt n)$。

但是在这题还卡空间，没关系。可以把询问离线下来，逐块地按照时间顺序处理询问。这样空间就可以做到线性了。

1.2 操作分块

如题，就是对询问序列上进行分块。

通常在答案有可合并性，修改和询问较为简单时可以对操作分块。

基本的思想就是将难以解决的问题用分块将所修改的信息简化到 $\mathcal O(B)$，然后对于每个块就可以用约 $\mathcal O(B^2)$ 的复杂度暴力计算（即对每个操作都将信息遍历），总复杂度就是 $\mathcal O(B^3)=\mathcal O(n\sqrt n)$。

1.2 例题

P5443 [APIO2019] 桥梁

给定有 $k$ 条边的带权无向图，有多次询问：

修改一条边的边权。

查询从一个点出发，走边权不超过 $m$ 的边可以到达的点的数量。

查询的本质相当于查询连通块的点的数量，可以用并查集维护。

不妨把所有询问序列分成多个大小为 $B$ 的块。把块内有关的边称为「块内边」，不在块内的边称为「无关边」。块内边的量级显然是 $\mathcal O(B)$ 的，而无关边的量级仍然为 $\mathcal O(k)$。考虑按照 $m$ 大小偏序，这样无关边只会在一个块内被增加 $1$ 次。对于块内边，由于只有 $\mathcal O(B)$，在每次查询中暴力添减即可。

具体来说，对于一次查询 $(u,m_i)$ 操作，依次进行：

撤销上一次询问的连的块内边，$\mathcal O(B)$。
连上满足边权 $\le m_i$ 的无关边，由于询问的 $m_i$ 是不减的，因此可以用一个指针维护，总复杂度是 $\mathcal O(k\log n)$。
连上块内符合条件边，$\mathcal O(B\log n)$，这个 $\log n$ 是可撤销并查集带来的。

然后查询子树大小就可以了。

复杂度为 $\mathcal O(\dfrac qB\log n(B^2+k)+k\log k)=\mathcal O(qB\log n+\dfrac {qk}B\log n)\ge\mathcal O(q\sqrt k\log n)$，在 $B=\sqrt k$ 取到。实际表现上块长取 $B=\sqrt{k\log k}$ 表现更优，可能是由于连无关边跑不满。

CF925E May Holidays

给出 $n$ 个点的树，点有点权 $w_i$ 和黑白两色。多次询问，每次可以修改单点的颜色，或者查询树上有多少白点 $u$，使得 $\operatorname{subtree}(u)$ 内黑点个数超过 $w_i$。

首先一步转化：设 $t_i=\begin{cases}-w_i,&{i\text{ is white.}}\-\infty,&i\text{ is black.}\end{cases}$，那么一次修改操作，就相当于在 $u$ 到根的链上对 $t_i$ 进行 $\pm1$ 操作，并将 $t_i$ 修改为 $-w_i/-\infty$，查询操作就相当于查全局有点权大于 $0$ 的点。

考虑按 $B$ 对查询序列进行分块，自然想到给块内所有被更改的点（下文称为「关键点」）建虚树，这样会把原树划分成多段。对于一个块，直接暴力重构，将每两个关键点的链单独拿出来，作为一段，对这一段内点的权值进行排序，并维护一个指针，表示首个权值为正的位置。每次对关键点的修改操作相当于对这个指针进行平移，因此操作可以在 $\mathcal O(1)$ 的时间内完成。

对于换颜色对自己带来的影响，可以维护一个 $sz_i$ 表示 $i$ 子树内的黑点数量。对于一个块中，直接用 lazy 标记对每一段进行操作。这个块结束后，再暴力对原树进行修改。

这样，每一个块的操作在 $\mathcal O(B^2+n\log n+n)=\mathcal O(n\log n+B^2)$ 的时间内完成，实际上排序这一过程由于值域只与树大小有关，所以可以优化到 $\mathcal O(n)$，即一个块的复杂度是 $\mathcal O(n+B^2)$ 的，总复杂度 $\mathcal O(\dfrac{n^2}B+ nB)\ge\mathcal O(n\sqrt n)$，在 $B=\sqrt n$ 时最优。

1.3 树上的分块操作

1.3.1 DFS 序分块

可以将树上问题转化为序列问题。但是在处理链操作时会多出树剖的 $\log n$ 复杂度。

1.3.2 轻重链剖分+序列分块

对于长度为 $k$ 的重链按照 $\sqrt k$ 分块。考虑跳轻边时子树大小至少减少一半，而重链长度不超过子树大小。因此单次操作的复杂度为 $\mathcal O(\sqrt n)+\mathcal O(\sqrt{\dfrac n2})+\mathcal O(\sqrt{\dfrac n4})+\cdots=\mathcal O(\sqrt n)$。然而仅适用于路径更改。

1.3.3 树分块

在 $n$ 个点的树上随机地撒 $\sqrt n$ 个关键点，相邻关键点距离期望为 $\mathcal O(\sqrt n)$。

https://oi-wiki.org/misc/mo-algo-on-tree/#%E7%9C%9F%E6%A0%91%E4%B8%8A%E8%8E%AB%E9%98%9F

Top Cluster 树分块

TBD.

1.3.4 例题

CF925E May Holidays

给出 $n$ 个点的树，点有点权 $w_i$ 和黑白两色。多次询问，每次可以修改单点的颜色，或者查询树上有多少白点 $u$，使得 $\operatorname{subtree}(u)$ 内黑点个数超过 $w_i$。

又出现喽。

对于一次修改操作，对于整块可以直接进行懒标记。在修改的同时维护全局答案，对于每个块维护桶，存对应元素的出现次数。新增或减少的部分就是值为 $1$ 的改变量，对于散块直接暴力更改即可。对于这个点，我们额外维护一个 $sz_i$ 表示 $i$ 子树中黑点个数，当 $i$ 从黑变白，$t_i$ 就是 $sz_i-w_i$。

可以直接用 DFS 序分块，时间复杂度带上树剖，为 $\mathcal O(n\sqrt n\log n)$。也可以轻重链剖分分块，即按照每个重链大小 $k$ 进行分块，考虑走一条轻边子树减少一半，重链点数不超过子树，因此复杂度为 $\sum\limits_{i=0}\mathcal O(\sqrt{2^{-i}k})=\mathcal O(\sqrt n)$，总复杂度为 $\mathcal O(n\sqrt n)$。但是常数较大，选 DFS 序分块没问题！

P8353 [SDOI/SXOI2022] 无处存储

维护数据结构，支持树上链加链求和。

$n\le 7\times10^6,q\le5\times10^4$。

64MB，5s

随机撒点，建虚树。

我写了再来看。（）https://www.luogu.com.cn/article/495a6tu0

1.4 根号分治

1.4.1 基本思想

核心思想是对全局设定阈值 $B$，分别对超过或不超过阈值的数据采用不同的方法处理，以达到复杂度的平衡。

通常令 $B=\sqrt n$，这样对于 $q\le \sqrt n$ 的问题可以 $\mathcal O(n\sqrt n)$ 预处理，对于 $q>\sqrt n$ 的问题可以 $\dfrac nq\le \sqrt n$ 地计算。

前文中的第二分块一题，复杂度的平衡上实际上就用了类似这一思想。

1.4.2 例题

P5309 [Ynoi2011] 初始化

给出长度为 $n$ 序列 $a_i$，多次查询。操作为区间求和，或者对下标模 $x$ 余 $y$ 者增 $z$。

$n\le 2\times10^5,a,z\le10^9+7$。

若 $x\ge\sqrt n$，那么直接暴力加维护块的前缀和，复杂度为 $\mathcal O(\sqrt n)$。

若 $x<\sqrt n$，考虑对相同的 $x,y$ 统计贡献。固定 $x$，维护 $y$ 的前后缀和。

每次查询分成两部分：一部分是 $x\ge\sqrt n$ 的部分，这部分可以直接对块求和求出。另一部分是 $x<\sqrt n$，可以枚举所有小于 $\sqrt n$ 的部分，然后根据前后缀和 $\mathcal 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


#include <iostream>

#define int long long

using namespace std;

const int N = 2e5 + 10;
const int B = 160;
const int P = 1e9 + 7;

int n, m;
int a[N];
int st[N / B + 10], ed[N / B + 10], pos[N], cnt;
int sum[N / B + 10], pre[B][B], suf[B][B];

inline int read () {
    int f = 1, ret = 0;
    char ch = getchar (); while (ch < '0' || ch > '9') {
        if (ch == '-') f = -f;
        ch = getchar ();
    }
    while (isdigit (ch)) ret = ret * 10 + ch - '0', ch = getchar ();
    return ret * f;
}

inline void add (int& x, const int& y) {
    x += y;
}

inline int qq (const int& l, const int& r) {
    int ret = 0;
    for (int i = l; i <= r; i ++) add (ret, a[i]);
    return ret;
}

inline int query (const int& l, const int& r) {
    int ret = 0;
    if (pos[l] == pos[r]) return qq (l, r);
    int L = pos[l] + 1, R = pos[r] - 1;
    for (int i = L; i <= R; i ++) add (ret, sum[i]);
    add (ret, qq (l, ed[pos[l]]));
    add (ret, qq (st[pos[r]], r));
    return ret;
}   

signed main (void) {

    n = read (); m = read ();
    for (int i = 1; i <= n; i ++) a[i] = read ();
    cnt = (n + B - 1) / B; for (int i = 1; i <= cnt; i ++) {
        st[i] = ed[i - 1] + 1; ed[i] = min (n, st[i] + B - 1);
        for (int j = st[i]; j <= ed[i]; j ++) pos[j] = i, add (sum[i], a[j]);
    } int x, y, z, l, r, ans;
    while (m --) {
        int opt; opt = read ();
        if (opt == 1) {
            x = read (), y = read (), z = read ();
            if (x >= B) for (int i = y; i <= n; i += x) add (a[i], z), add (sum[pos[i]], z);
            else {
                for (int i = y; i <= x; i ++) add (pre[x][i], z); 
                for (int i = y; i; i --)      add (suf[x][i], z);
            }
        } else { l = read (), r = read ();
            ans = query (l, r);
            for (int i = 1; i < B; i ++) {
                int L = (l - 1) / i + 1, R = (r - 1) / i + 1;
                if (L == R) add (ans, pre[i][(r - 1) % i + 1] + P - pre[i][(l - 1) % i]);
                else        add (ans, ((R - L - 1) *  pre[i][i] + pre[i][(r - 1) % i + 1] + suf[i][(l - 1) % i + 1]));
            }
            printf ("%d\n", ans % P);
        }
    }
    
    return 0;
}

2. 莫队

2.1 概述

莫队算法是一种离线算法。

$k$ 维莫队的状态可以用一个 $k$ 元组表示。当得知一个状态信息时，可以用较小的代价转移到该状态的相邻状态时，可以使用莫队算法。

莫队算法对所有目标状态按照某种方式排序，尽可能减小「转移到相邻状态」的次数。

2.2 普通莫队

常见形式为：不带修区间查询。

长度为 $n$ 的序列，$m$ 次查询，转移到相邻状态的复杂度为 $\mathcal O(1)$。将序列按照 $\dfrac{n}{\sqrt m}$ 为块长进行分块，对询问进行排序，第一关键字是左端点所在块，第二关键字为右端点。这样就能达到最优复杂度 $\mathcal O(n\sqrt m)$。

假设 $n,m$ 同阶，三维莫队的最优复杂度可以达到 $\mathcal O(n^{\frac 53})$。按照 $\mathcal n^{\frac 23}$ 分块即可。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void solve (int l, int r) { // 初始状态
sort (qry.begin (), qry.end ());
for (const auto& [ql, qr, id] : qry) {
    while (l > ql) move (-- l, 1);
    while (r < qr) move (++ r, 1);
    while (l < ql) move (l ++, -1);
    while (r > qr) move (r ++, -1);
    ans[id] = ansnow;
}
}

这里的 while 循环，必须是先进行扩大区间操作，再进行缩小区间操作。

2.2.1 例题

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

给出长度为 $n$ 的序列 $a_i$，每次给出两个数 $l,r$，求 $[l,r]$ 中随机抽出两个 $i\not=j$，$a_i=a_j$ 的概率。

对于 $(i,i)$ 的询问，仅有一个元素，显然答案为 $0$。

设当前状态中，$col_i$ 表示颜色 $i$ 出现的次数，$ans$ 表示当前的可行配对方案。假设当前移动到的颜色为 $c$，那么增长就是 $ans\gets ans+\dbinom{col_c+1}2-\dbinom{col_c}2$，缩短为 $ans\gets ans-\left(\dbinom{col_c}2-\dbinom{col_c-1}2\right)$。那么当前询问的答案即为 $\dfrac{ans}{\dbinom{r-l+1}2}$。

复杂度为 $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


void prework () {
    cnt = len = sqrt (n); 
    if (len * len != n) cnt ++;
    for (int i = 1; i <= cnt; i ++) {
        L[i] = R[i - 1] + 1;
        R[i] = min (n, len * i);
    }
    for (int i = 1; i <= cnt; i ++)
        for (int j = L[i]; j <= R[i]; j ++)
            bel[j] = i;

    sort (q + 1, q + m + 1, [&](auto x, auto y) { return bel[x.l] == bel[y.l] ? ((bel[x.l] & 1) ? x.r > y.r : x.r < y.r) : bel[x.l] < bel[y.l]; });
}

void add (int c) {
    sum += ccnt[c];
    ccnt[c] ++;
}

void del (int c) {
    ccnt[c] --;
    sum -= ccnt[c];
}

for (int i = 1, l = 1, r = 0; i <= m; i ++) {
    if (q[i].l == q[i].r) {
        ans1[ q[i].id ] = 0, ans2[ q[i].id ] = 1;
        continue;
    }

    while (l > q[i].l) add (c[-- l]);
    while (r < q[i].r) add (c[++ r]);
    while (l < q[i].l) del (c[l ++]);
    while (r > q[i].r) del (c[r --]);
    ans1[ q[i].id ] = sum;
    ans2[ q[i].id ] = 1ll * (r - l + 1) * (r - l) / 2;
}

组合数前缀和

多次询问，每次给出 $n,m$ 求 $\sum\limits_{i=0}^m \dbinom ni$。

设 $f(n,m)=\sum\limits_{i=0}^m \dbinom ni$。由 $\dbinom nm=\dbinom {n-1}m+\dbinom{n-1}{m-1}$，有 $f(n,m)=\sum\limits_{i=0}^m \dbinom{n-1}i+\sum\limits_{i=0}^{m-1} \dbinom{n-1}i=2f(n-1,m)-\dbinom{n-1}{m}$，可以在 $f(n,k)$ 与 $f(n-1,k)$ 间转移。$f(n,k+1)=f(n,k)+\dbinom n{k+1}$，可以在 $f(n,k)$ 与 $f(n,k-1)$ 间转移。

2.3 带修莫队

实际上就是在普通的莫队上加上一个时间维度。

2.3.1 例题

P1903 [国家集训队] 数颜色 / 维护队列 /【模板】带修莫队

给出长度为 $n$ 的颜色序列。多次询问。

每次询问给出 $[l,r]$，求 $[l,r]$ 内不同颜色数量。也可以修改某个位置的颜色。

用 $[l,r,tim]$ 表示 $tim$ 时刻 $l,r$ 的答案。根据 2.1 中的内容，设 $B=n^{\frac23}$，按照 $l$ 所在块为第一关键字，以 $r$ 所在块为第二关键字，以 $tim$ 为第三关键字排序。

然后跑莫队即可。复杂度为 $\mathcal O(n^{\frac 53})$。

 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


#include <map>
#include <array>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1.5e5;

int n, q, B;
int c[N], tim, now[N], ans[N], res, ii, dudu;
int col[N * 10];
vector < array <int, 4> > qry;
vector < pair <int, int> > change;

bool cmp (array <int, 4> x, array <int, 4> y) {
    if ((x[0] + B - 1) / B != (y[0] + B - 1) / B) return (x[0] + B - 1) / B < (y[0] + B - 1) / B;
    if ((x[1] + B - 1) / B != (y[1] + B - 1) / B) return (x[1] + B - 1) / B < (y[1] + B - 1) / B;
    return x[2] < y[2];
}

void add (int u) {
    col[u] ++;
    if (col[u] == 1) ++ res;
}

void del (int u) {
    col[u] --;
    if (col[u] == 0) -- res;
}

int l = 1, r = 0, t = 0;

void upd (int t) { 
    t --;
    if (l <= change[t].first && change[t].first <= r) del (c[change[t].first]), add (change[t].second);
    swap (c[change[t].first], change[t].second);
}

int main (void) {

    scanf ("%d%d", &n, &q); B = pow (n, 0.67);
    for (int i = 1; i <= n; i ++) scanf ("%d", c + i);
    for (int i = 1; i <= q; i ++) {
        char typ[5]; int x, y;
        scanf ("%s%d%d", typ + 1, &x, &y);
        if (typ[1] == 'R') change.push_back ({x, y});
        else    qry.push_back ({x, y, (int)change.size (), (int)qry.size () + 1});
    }
    
    sort (qry.begin (), qry.end (), cmp);
    for (auto& [ql, qr, qt, aid] : qry) {
        while (l > ql) add (c[-- l]);
        while (l < ql) del (c[l ++]);
        while (r > qr) del (c[r --]);
        while (r < qr) add (c[++ r]);
        while (t < qt) upd (++ t);
        while (t > qt) upd (t --);
        ans[aid] = res;
    }

    for (int i = 1; i <= qry.size (); i ++) printf ("%d\n", ans[i]);

    return 0;
}

2.4 树上莫队

2.4.1 假·树上莫队

一般用于处理询问树上路径相关信息的问题。

考虑写出访问的欧拉序，也就是第一次访问和最后一次访问分别入队。大概是括号序列的形式。

设 $i$ 第一次出现的位置为 $s_i$，访问完的位置为 $t_i$。那么我们令一次访问到关于节点 $i$ 的位置，先「加入」，下一步「弹出」，以此类推。类似于异或操作。

若 $u$ 是 $v$ 祖先，则依次进行 $[s_u,s_v]$ 这一段的操作相当于将 $u\to v$ 路径上所有点进行「加入」操作。可以发现对于非路径上的节点，若访问，则一定会在访问路径上之前结束访问，即「加入」且「弹出」。
若 $u,v$ 无祖孙关系，则依次进行 $[t_u,s_u]$ 操作，再进行二者 LCA 操作。与上面是类似的。

SP10707 COT2 - Count on a tree II

给出 $n$ 个节点的树，点有色。多次询问，问 $u\to v$ 路径上颜色数。

跟着上文介绍的方法跑莫队即可。

 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


#include <array>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40010;
const int Q = 1e5 + 10;

int n, m;
vector <int> g[N];
int s[N], t[N], tim, c[N], B;
int fa[N][20], dep[N];
int w[N << 1], ans[Q], col[N], res;
bool used[N];
vector < array <int, 4> > qry;

void dfs (int u) {
    dep[u] = dep[fa[u][0]] + 1;
    s[u] = ++ tim; w[tim] = u;
    for (int i = 1; i < 20; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : g[u]) if (v != fa[u][0]) fa[v][0] = u, dfs (v);
    t[u] = ++ tim; w[tim] = u;
}

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

void modify (int u) {
    if (used[u]) if (!-- col[c[u]]) -- res;
    if (!used[u]) if (++ col[c[u]] == 1) ++ res;
    used[u] ^= 1;
}

int main (void) {

    scanf ("%d%d", &n, &m); B = sqrt (n); vector <int> tmp;
    for (int i = 1; i <= n; i ++) scanf ("%d", c + i), tmp.push_back (c[i]); sort (tmp.begin (), tmp.end ()); tmp.erase (unique (tmp.begin (), tmp.end ()), tmp.end ());
    for (int i = 1; i <= n; i ++) c[i] = lower_bound (tmp.begin (), tmp.end (), c[i]) - tmp.begin () + 1;
    for (int i = 1; i < n; i ++) {
        int u, v; scanf ("%d%d", &u, &v);
        g[u].push_back (v); g[v].push_back (u);
    } dfs (1);
    for (int i = 1; i <= m; i ++) {
        int u, v; scanf ("%d%d", &u, &v);
        if (s[u] > s[v]) swap (u, v);
        int lc = lca (u, v);    
        if (lc == u) qry.push_back ({s[u], s[v], i, 0});
        else         qry.push_back ({t[u], s[v], i, lc});
    }

    sort (qry.begin (), qry.end (), [&](auto x, auto y) { return (x[0] + B - 1) / B != (y[0] + B - 1) / B ? (x[0] + B - 1) / B < (y[0] + B - 1) / B : x[1] < y[1]; });
    int l = 1, r = 0;
    for (auto& [ql, qr, i, lca] : qry) {
        while (l > ql) modify (w[-- l]);
        while (r < qr) modify (w[++ r]);
        while (l < ql) modify (w[l ++]);
        while (r > qr) modify (w[r --]); 
        if (lca) modify (lca);
        ans[i] = res;
        if (lca) modify (lca);
    }
    for (int i = 1; i <= m; i ++) printf ("%d\n", ans[i]);

    return 0;
}

2.4.2 真·树上莫队

TBD

2.5 回滚莫队（不删除/插入莫队）

对于类似 $\max/\min$ 一类不支持删除、插入的操作，普通的莫队算法难以处理。因此就诞生了「回滚莫队」。

考虑对同一个块中的左端点同时处理，按照右端点排序，这样满足了右端点的单调性。对于每个询问，先移动右端点，再移动左端点。处理后撤回左端点移动的影响，也就是移回来。

2.5.1 基本流程

下面以不删除为例，不插入是类似的。

分类：以将询问按照 $l$ 所在块分成多类。对于同一类的询问，按照 $r$ 升序排序。
块内询问：对于 $r$ 在块内的询问，直接暴力求解即可，$\mathcal O(\sqrt n)$。
块外询问：对于 $r$ 在块外的询问，维护 $(ed_l,r]$ 的部分。由于 $r$ 升序，因此这部分不会删除。对于 $[l,ed_l]$ 部分，每次暴力插入即可，$\mathcal O(n+q\sqrt n)$。

2.5.2 例题

JOISC2014 C-歴史の研究

给出位置有颜色的序列。

每次询问给出区间 $[l,r]$，设颜色 $k$ 的价值为 $k$ 在 $[l,r]$ 内出现次数与 $k$ 之积。求 $[l,r]$ 出现颜色的最大价值。

模板题啊！维护每个颜色的出现次数，每次新增就检查这个新增的颜色是否是新答案即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


int R = 0; ll maxans = 0;
for (int i = 1; i < qry.size (); i ++) {
    auto& [l, r, id] = qry[i];
    if (pos[l] != pos[qry[i - 1][0]]) {
        R = ed[pos[l]];
        for (int i = 0; i < tmp.size (); i ++) col[i] = 0;
        maxans = 0;
    }

    if (pos[r] == pos[l]) {
        for (int j = l; j <= r; j ++) ans[id] = max (ans[id], (++ col[a[j]]) * 1ll * tmp[a[j]]);
        for (int j = l; j <= r; j ++) col[a[j]] --;
        maxans = 0;
    } else {
        while (R < r) {
            ++ R; ++ col[a[R]];
            maxans = max (maxans, col[a[R]] * 1ll * tmp[a[R]]);
        }
        ans[id] = maxans;
        for (int j = l; j <= ed[pos[l]]; j ++) ans[id] = max (ans[id], (++ col[a[j]]) * 1ll * tmp[a[j]]); 
        for (int j = l; j <= ed[pos[l]]; j ++) -- col[a[j]]; 
    }
}

P8078 [WC2022] 秃子酋长

给出排列 $a_i$，多次询问：$[l,r]$ 这段数排序后，求相邻数字在原序列下标差绝对值之和。

考虑 不插入莫队。

第一关键字相同，以 $r$ 为第二关键字降序排序。

先把全局 $[1,n]$ 的答案算出来，这部分是很好算的。在一个块内，对于一个询问 $[l,r]$，维护永久指针 $R$，表示当前删到的右端点。这一过程可以用 $\mathcal O(1)$ 插删的链表维护。

2.6 二次离线莫队

对于单次转移复杂度较高的问题，用普通莫队难以实现。可以将莫队与扫描线结合，使复杂度由 $\mathcal O(nk\sqrt n)$ 降到 $\mathcal O(nk+n\sqrt n)$。一般用于一个数的贡献与区间内的数有关，设 $f(x,l,r)$ 表示 $x$ 对区间 $[l,r]$ 的贡献。

考虑区间端点变化的影响。每一次询问显然可以转化为求 $f(x,l,x-1)$ 和的形式。差分，有 $f(x,l,x-1)=f(x,1,x-1)-f(x,1,l-1)$。

这样就转化成了数对前缀的贡献，维护所有数对前缀和的贡献即可。

这一点可以预处理做到。观察上式，实际上有用的只有 $f(i,1,i-1)$ 以及 $f(i,1,l-1)$。对于前者，直接维护。对于 $f(i,1,l-1)$，维护一个值 $v$，表示 $l=st_{block-1}$ 的值，这显然是可以增量维护的。因而对于一次查询，查找 $f(i,1,l-1)$ 的复杂度是 $k\sqrt n$，总复杂度仍然是 $\mathcal O(nk+n\sqrt n)$，但空间复杂度降到了 $\mathcal O(n)$。

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

给出长度为 $n$ 的序列 $a_i$，多次查询，查询 $i,j\in[l,r],i<j$ 的满足 $a_i\oplus a_j$ 二进制下有 $k$ 个 $1$ 的点对数。

$n\le 10^5,a_i<2^{14}$。

如果直接莫队，一次插入的复杂度要枚举 $\dbinom{14}{k}\le3432$ 个元素，极大常数，难以接受。

考虑二次离线莫队。设 $f(x,l,r)$ 表示 $x$ 对 $[l,r]$ 的贡献，那么从 $[l,r]$ 转移到 $[l,r+1]$ 的贡献就是 $f(r+1,l,r)=f(r+1,1,r)-f(r+1,1,l-1)$，从 $[l,r]$ 转移到 $[l,r-1]$ 贡献就是 $-f(r,l,r-1)=-f(r,1,r-1)+f(r,1,l-1)$。根据上面的技巧，可以维护一个 $v_i$，表示到 $f(i,1,i-1)$ 的值。

故总复杂度为 $\mathcal O(n\sqrt n+n\max a_i)$。

TBD.