0x44 分 块

在前面两节中，我们探讨了树状数组与线段树两种数据结构。树状数组基于二进制划分与倍增思想，线段树基于分治思想。它们之所以能够高效地在一个序列上执行指令

并统计信息，就是因为它们把序列中的元素聚合成大大小小的“段”，花费额外的代价对这些“段”进行维护，从而使得每个区间的信息可以快速由几个已有的“段”结合而成。

当然，树状数组与线段树也有其缺点。比如在维护较为复杂的信息（尤其是不满足区间可加、可减性的信息）时显得吃力，代码实现也不是那么简单、直观，需要深入理解并注意许多细节。在本节中，我们将介绍分块算法。分块的基本思想是通过适当的划分，预处理一部分信息并保存下来，用空间换取时间，达到时空平衡。事实上，分块更接近于“朴素”，效率往往比不上树状数组与线段树，但是它更加通用、容易实现。我们通过几道例题详细探讨各种形式的分块算法及其应用。

【例题】A Simple Problem with Integers POJ3468

给定长度为 $N(N\leq 10^{5})$ 的数列 $A$ ，然后输入 $Q(Q\leq 10^{5})$ 行操作指令。

第一类指令形如“C l r d”，表示把数列中第 $l \sim r$ 个数都加 $d$ 。

第二类指令形如“Q $l$ r”，表示询问数列中第 $l\sim r$ 个数的和。

我们已经用树状数组和线段树在 $O((N + Q)\log N)$ 的时间内解决过该问题。现在我们用分块来再次求解。

把数列 $A$ 分成若干个长度不超过 $\lfloor \sqrt{N}\rfloor$ 的段，其中第 $i$ 段左端点为 $(i - 1)\lfloor \sqrt{N}\rfloor +$ 1，右端点为 $\min (i\lfloor \sqrt{N}\rfloor ,N)$ ，如下图所示。

另外，预处理出数组sum，其中 $sum[i]$ 表示第 $i$ 段的区间和。设 $add[i]$ 表示第 $i$ 段的“增量标记”，起初 $add[i] = 0$ 。

对于指令“C l r d”：

1. 若 $l$ 与 $r$ 同时处于第 $i$ 段内，则直接把 $A[l], A[l + 1], \dots, A[r]$ 都加 $d$ ，同时令 $sum[i] + = d * (r - l + 1)$ 。

2. 否则，设 $l$ 处于第 $p$ 段， $r$ 处于第 $q$ 段。

(1) 对于 $i \in [p + 1, q - 1]$ ，令 $add[i] += d$ 。

(2) 对于开头、结尾不足一整段的两部分，按照与第1种情况相同的方法朴素地更新。

该指令的操作方法如下页图所示。

$[\mathbf{L}, \mathbf{R}]$ 分成若干个整段处理， $[1, L]$ 、 $(R, r]$ 不足整段，暴力处理

对于指令“Q $l$ r”：

1. 若 $l$ 与 $r$ 同时处于第 $i$ 段内，则 $(A[l] + A[l + 1] + \dots + A[r]) + (r - l + 1) * add[i]$ 就是答案。

2. 否则，设 $l$ 处于第 $p$ 段， $r$ 处于第 $q$ 段，初始化 $ans = 0$ 。

(1) 对于 $i \in [p + 1, q - 1]$ , 令 $ans += sum[i] + add[i] * len[i]$ , 其中 $len[i]$ 表示第 $i$ 段的长度。
(2) 对于开头、结尾不足一整段的两部分，按照与第1种情况相同的方法朴素地累加。

这种分块算法对于整段的修改用标记add记录，对于不足整段的修改采取朴素算法。因为段数和段长都是 $O(\sqrt{N})$ ，所以整个算法的时间复杂度为 $\mathrm{O}\big((N + Q)*\sqrt{N}\big)$ 。大部分常见的分块思想都可以用“大段维护、局部朴素”来形容。

long long a[100010],sum[100010],add[100010];   
int L[100010],R[100010]；//每段左右端点   
int pos[100010]；//每个位置属于哪一段   
int n,m,t;   
void change(int l,int r,long long d){ int  $\mathsf{p} =$  pos[l]，q  $=$  pos[r]; if  $(\mathsf{p} = =\mathsf{q})$  { for (int i  $= 1$  ;i  $\Leftarrow$  r;i++)a[i]  $+ =$  d; sum[p]  $+ =$  d\*(r-1+1); } else{ for (int i  $= p + 1$  ;i  $\Leftarrow$  q-1;i++)add[i]  $+ =$  d; for (int i  $= 1$  ;i  $\Leftarrow$  R[p];i++)a[i]  $+ =$  d; sum[p]  $+ =$  d\*(R[p]-1+1); for (int i  $= \mathsf{L}[\mathsf{q}]$  ;i  $\Leftarrow$  r; i++)a[i]  $+ =$  d; sum[q]  $+ =$  d\*(r-L[q]+1); }   
}

long long ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = 1; i <= r; i++) ans += a[i];
        ans += add[p] * (r - 1 + 1);
    }
    else {
        for (int i = p + 1; i <= q - 1; i++) ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = 1; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - 1 + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}

scanf("%s%d%d", op, &l, &r);
if (op[0] == 'C') {
    scanf("%d", &d);
    change(l, r, d);
}
else printf("%lld\n", ask(l, r));
}

★【例题】蒲公英 BZOJ2724

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ 。其中 $a_i$ 为一个正整数，表示第 $i$ 棵蒲公英的种类编号。

接下来有 $m$ 次询问，每次询问一个区间 $[x, y]$ ，你需要回答 $a_x, a_{x+1}, \dots, a_y$ 里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。 $n\leq 4*10^4,m\leq 5*10^5,a_i\leq 10^9$

本题是经典的在线求区间众数问题。因为众数不具有“区间可加性”（已知序列 $a$ 中区间 $[x, y]$ 的众数和区间 $[y + 1, z]$ 的众数，不能直接得到区间 $[x, z]$ 的众数），所以用树状数组或线段树维护就十分困难。下面我们介绍两种常见的分块做法。

若把序列 $a$ 分成 $T$ 块，则每块的长度 $L = N / T$ ，我们稍后会讨论 $T$ 的取值。

对于每个询问 $[l, r]$ ，设 $l$ 处于第 $p$ 块， $r$ 处于第 $q$ 块。与上一道题一样，我们把区间 $[l, r]$ 分成三部分：

1. 开头不足一整段的 $[l, L)$ 。

2. 第 $p + 1 \sim q - 1$ 块构成的区间 $[L, R]$ 。

3. 结尾不足一整段的 $(R, r]$ 。

显然， $a$ 序列在区间 $[l,r]$ 中的众数只可能来自以下两种情况：

1. 区间 $[L, R]$ 的众数。

2. 出现在 $[l, L)$ 与 $(R, r]$ 之间的数。

方法一

预处理出所有以“段边界”为端点的区间 $[L, R]$ 中每个数出现的次数，以及区间众数。这样的区间共有 $O(T^{2})$ 个，并且保存每个数出现的次数需要长度为 $O(N)$ 的数组（记为 $cnt_{L,R}$ ）。

对于每个询问中的 $[l, L)$ 与 $(R, r]$ ，可以通过朴素扫描，在数组 $cnt_{L,R}$ 的基础上累加次数，从而更新答案。回答询问后再进行一次朴素扫描，从 $cnt_{L,R}$ 中减少次数，把数组复原。

这个算法的时间为 $O(NT^2 + MN / T)$ ，空间为 $O(NT^2)$ 。不妨设 $N, M$ 为相同数量级，通过方程 $NT^2 = MN / T$ ，可解得 $T \approx \sqrt[3]{N}$ ，此时整个算法的复杂度在 $O(N^{5/3})$ 级别。

方法二

在预处理时，只保存所有以“段边界”为端点的区间 $[L, R]$ 的众数。另外，对每个数值建立一个STL vector，按顺序保存该数值在序列 $a$ 中每次出现的位置。

对于每个询问，扫描 $[l, L)$ 与 $(R, r]$ 中的每个数 $x$ ，在对应的 vector 里二分查找即可得到 $x$ 在 $[l, r]$ 中出现的次数，从而更新答案。

例如序列 $a = \{1,4,2,3,2,4,3,2,1,4\}$ ，数值1出现的位置为 $\{1,9\}$ ，数值2出现的位置为 $\{3,5,8\}$ ，数值3出现的位置为 $\{4,7\}$ ，数值4出现的位置为 $\{2,6,10\}$ 。假设 $l = 2$ ， $r = 8$ ，若要求数值2在序列 $a$ 的区间 $[l,r]$ 中出现多少次，则应该在 $\{3,5,8\}$ 中二分查找第一个 $\geq l$ 的数，得到3（下标为0）；二分查找最后一个 $\leq r$ 的数，得到8（下标为2）。把两个下标相减再加1，得到答案：3次。

这个算法的时间为 $O(NT + MN / T*\log N)$ ，空间为 $O(T^{2})$ 。应取 $T = \sqrt{N\log N}$ ，此时整个算法的复杂度在 $O\left(N\sqrt{N\log N}\right)$ 级别。

【例题】磁力块 ContestHunter#46-A

在一片广袤无垠的原野上，散落着 $N$ 块磁石。每个磁石的性质可以用一个五元组 $(x, y, m, p, r)$ 描述，其中 $x, y$ 表示其坐标， $m$ 是磁石的质量， $p$ 是磁力， $r$ 是吸引半径。

小Q带着一块自己的磁石 $L$ 来到了这片原野的 $(x_0,y_0)$ 处。他手持磁石 $L$ 并保持

原地不动，所有可以被 $L$ 吸引的磁石将会被吸引过来。在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是最初携带的 $L$ 磁石）在 $(x_0, y_0)$ 处吸引更多的磁石。

磁石 $A$ 可以吸引磁石 $B$ 的条件是：磁石 $A$ 位于 $(x_0, y_0)$ ，并且磁石 $A$ 与磁石 $B$ 的距离不大于磁石 $A$ 的吸引半径，磁石 $B$ 的质量不大于磁石 $A$ 的磁力。特别地，只有小 Q 手持的磁石才会吸引其他磁石，原野上散落的磁石之间不会互相吸引。

小Q想知道，他最多能获得多少块磁石呢？ $1\leq N\leq 250000$

我们可以执行一个BFS框架，建立一个队列，最初仅包含磁石 $L$ ，每次从队头取出磁石，把所有能被吸引的磁石加入队尾。

接下来我们需要解决的问题就是判断哪些磁石能被吸引。本题中，磁石吸引条件包含两个维度，即质量 $\leq$ 磁力、距离 $\leq$ 吸引半径，使用平衡树等数据结构进行维护会比较复杂。这时分块算法就是一个不错的选择。

把 $N$ 块磁石按照质量排序，分成 $\sqrt{N}$ 段。然后在每段内部，再重新按照距离排序。

每次用队头磁石（设为 $H$ ）吸引其他磁石时，根据排序的结果，一定存在一个整数 $k$ ，满足：

1. 第 $1 \sim k - 1$ 段中的所有磁石质量都不大于 $H$ 的磁力。

2. 第 $k + 1$ 段之后的磁石质量都大于 $H$ 的磁力，不可能被吸引。

因为每一段内部已经按照距离重新排序，所以第 $1 \sim k - 1$ 段中与 $(x_0, y_0)$ 的距离小于 $H$ 吸引半径的磁石必定处于每段的开头部分。我们直接在第 $1 \sim k - 1$ 段中，从每段左端开始逐一扫描，把能吸引的磁石加入队尾，直至第一个不能被吸引的磁石（记为 $P$ ）。之后，我们把该段的开头位置移到 $P$ 处。这样一来，被吸引的磁石就不会被重复扫描。所以对于每一段来说，上述扫描过程的均摊复杂度为 $O(1)$ ，处理全部 $k - 1$ 段的复杂度为 $O(\sqrt{N})$ 。

对于第 $k$ 段，朴素扫描该段，把能被吸引的磁石取走，复杂度为 $0(\sqrt{N})$ 。

整个算法的时间复杂度为 $O(N\sqrt{N})$

*【例题】小Z的袜子 BZOJ2038

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命。

具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R的袜子中随机选出两只来穿。尽管小Z并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希

望这个概率尽量高，所以他可能会询问多个 $(L, R)$ 以方便自己选择。

$N \leq 50000$ ，询问次数 $\leq 50000$ ，袜子颜色数 $\leq N$ 。

在本题中，我们将介绍分块算法的一种重要形式——对“询问”进行分块。这是一种离线做法，我们先把所有询问 $[l, r]$ 读入，把这些询问按照左端点递增排序，然后分成 $\sqrt{N}$ 块。每块内部再按照右端点排序。

这样一来，在每一块内部，相邻两个询问的左端点变化在 $\sqrt{N}$ 以内，右端点变化是单调的。如果我们利用上一次询问的回答为基础，那么每次只需要花费 $O\left(\sqrt{N}\right)$ 的时间处理左端多出或减少的部分。而整块中右端点增长的范围之和为 $O(N)$ ，所以在 $O\left(N\sqrt{N}\right)$ 的时间内即可求解本题。

具体来说，对于每一块询问，我们先朴素处理该块的第一个询问，得到一个数组num,表示在该块的第一个询问区间 $[l,r]$ 中，颜色为 $c$ 的袜子有num[c]只。另外，我们再维护一个变量ans，存储 $\sum_{c}num[c]*(num[c] - 1) / 2$

然后，我们依次考虑该块的其余询问。当左、右端点发生变化时，朴素地在 num 数组中进行增减，同时更新 ans 的值。显然，抽到同色袜子的概率就是 $\frac{ans}{C_{r - l + 1}^2}$ 。