Update: 2026.1.15 byx

---

分块应用举例

1. P4168 蒲公英

【题意简化】给定一个长度为 $n$ 的序列， $m$ 次询问区间众数。$(1 \leq n \leq 40000,1 \leq m \leq 50000,1S,512M)$

【分析】本题是经典的在线求区间众数的问题(不修改，只询问,在线)。区间众数不具有“区间可加性”，用树状数组、线段树维护就很困难。可以用分块加上计数桶数组的思想解决。由于要求在线，也无法使用莫队。

定义 $s[i][j]$ 前 $i$ 块 $j$ 出现的次数, $f[i][j]$ 第 $i$ 块到第 $j$ 块的众数，提前预处理计算出这两个数组，时间复杂度 $O(\sqrt{N}|a_i|+\sqrt{N}\times \sqrt{N} \times \sqrt{N})$,$|a_i|$ 表示 $a_i$ 的值域，离散化后就是 $N$.

需要使用一个临时计数数组 $t[j]$ 记录 $j$ 出现的次数。为了清零，不要每次使用的时候都 memset，使用完后，修改了那一段整队那一段清零。

询问 $[l,r]$ 区间众数，如果 $p=l/len,q=r/len$( $p$,$q$ 表示所处的块编号)，第 $p+1$ 到 $q-1$ 块是整段包含的，众数就是 $f[i][j]$ , 局部 $[l，ed[p])$ 和 $[st[q],r]$ 扫描每一个数，计算其出现的次数，保留出现次数最多的数就是答案，查询时间复杂度就是 $O(m \times ( \sqrt{N}+ \sqrt{N}))$

参考代码：点击

2. P5048 Ynoi2019 模拟赛 Yuno loves sqrt technology III

【题意简化】：给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的众数的出现次数，强制在线。($1 \leq n,m \leq 10^5,2S,62M$)

【分析】在线维护区间众数出现的次数，空间限制很小，$O(n\sqrt{n})$ 空间肯定会 $MLE$，需要设计出 $O(n)$ 空间限制的做法。

分块本质就是整块整体维护，朴素处理局部零散段。num[i][j] 表示第 i 块到第 j 块众数出现的次数，提前预处理好。 vector<int>g[N] , 将值相同的下标位置放在同一行，p[i] 表示 a[i] 在 vector 中存储的位置。 当前众数出现次数为 ret , 那么在 g[a[i]] 从 p[i] 往后找 ret 个数，如果没有超过查询右端点, 那么答案肯定要至少加一。通过这种方法求出 a[i] 出现次数。

本题比较巧的地方就是利用 vector 方便零散块内处理 a[i] 在整段中出现次数是否超过原总数次数。

【参考代码】点击

3. P2801 教主的魔法

【题意简化】两种操作：

• 给区间 $[l,r]$ 加一个数 $c$

• 查询区间 $[l,r]$ 大于等于 $c$ 的个数

【分析】可以使用分块，每一块内排序，块内是有序的，可以利用二分查找，找的大于等于 $c$ 的个数, 但是又不能在原始序列上排序，否则修改的到块的内部，就没办法修改了，可以利用增加一个辅助数组，长度与原始数组相等，在辅助数组内进行排序。 假如分成 $num$ 块,则块长度为 $\frac{n}{num}$ , 块内直接暴力修改、查询, 块整体修改, 只需要在“增量数组”上修改就可以了，查询的时候在辅助有序数组上二分查找。$q$ 次修改、查询，时间复杂度就为： $O(q\sqrt{n} \log_{}{n})$

本质就是分块，块内增加排好序的辅助数组，方便二分查找。

参考代码： 点击

4. P4135 作诗

【题意简化】：给定长度为 $n$ 的整数序列，$m$ 次询问区间 $[l,r]$ 中出现正偶数次的数的个数。($1 \leq n,m \leq 10^5,512M$)

【分析】 预处理出：pre[i][j] 前 i 块 j 出现的次数 ，even[i][j] 第 i 块到第 j 块出现偶数次的种类数 。

询问的时候，只需要考虑前后零头块与整个块对答案的贡献，利用辅助计数数组计算 a[j] 在前后零头块出现的次数，利用 pre[i][a[j]] ,可以计算出 a[j] 在整块 bl+1 到 br-1 出现的次数, 分类讨论 a[j] 对答案的贡献。

【参考代码】点击

5. P3203 弹飞绵羊

【题意简化】水平直线上有 $n(2\times 10^5)$ 个位置，每个位置 $i$ 上有一个弹射装置，系数为 $k_i$，可以将绵羊弹射到 $i+k_i$ 的位置。

进行 $m(10^5)$ 次操作，修改操作: 将 $j$ 位置的系数改为 $k$ ; 询问操作：请输出绵羊在位置 $j$ ,经过几次被弹射到 $n$ 以外。

【分析】直接暴力模拟弹射过程，时间复杂度是 $O(nm)$. 标准解法是 LCT , 这里提供一种分块的简单写法，本质思想就是利用分块，在块与块之间跳，修改也容易维护。

内块要维护两个重要信息，b[i] 表示从位置 i 出发跳几次跳到下一个块，to[i] 表示从位置 i 出发跳到下一个块的次数。从大到小枚举位置 i ,当 i+k[i]>ed[belong[i]] 时, 说明跳 1 步就可以跳到下一块, 跳到的位置是 i+k[i] , 即 b[i]=1,to[i]=i+k[i] ; 当 i+k[i]<=ed[belong[i]] 时，说明跳一次没有跳出本快，那么 b[i]=b[i+k[i]]+1,to[i]=to[i+k[i]] ;

修改的时候，只需要修改位置 $j$ 所在块的 b[j],to[j] 的信息就可以了。

时间复杂度分析，块间跳跃，一次询问复杂度就是快数，一次修改时间复杂度就是块长。块长为 $\sqrt{n}$ , 那么时间复杂度就是 $O(m\sqrt{N})$

【参考代码】点击

6.P10590 磁力块

【题意简化】二维平面上给定 $n$ 个散落的磁铁。每个磁铁给定 $5$ 个属性 $(x,y,m,p,r)$ ,其中 $x,y$ 代表坐标，$m$ 是磁石质量，$p$ 是磁力，$r$ 是吸引半径。

小 $Q$ 在 $(x_0,y_0)$ 位置，带着一个磁石 $L$ ,他举着磁石保持原地不动，吸引其他散落的磁石。当然每次他都可以更好任意一块已经获得的磁石。磁石 A 能够吸引磁石 B 的条件是：A 位于 $(x_0,y_0)$ ，并且磁石 A 与磁石 B 的距离不大于磁石 A 的吸引半径，磁石 A 的磁力大于等于 B 的质量。 注意，只有小 Q 拿着磁石才会吸引其他磁石，散落的磁石之间不会相互吸引。

小 $Q$ 最多能获得多少块磁石？$(1\le n \le 250000)$

【分析】分块好题，BFS+分块。

整体就是一个 BFS 框架，将最初磁石入队，每次取出队首，把能够吸引到的磁石加入队尾。直接扫描所有磁石，时间复杂度是 $O(n^2)$。

解下思考如何高效判断哪些磁石能被吸引。磁石吸引条件是两个维度，即 质量 小于等于 磁力、距离 小于等于 吸引半径，使用平衡树或者树套树比较复杂。分块相对比较简单。

把 $N$ 块磁石按照质量排序，分成 $\sqrt{N}$ 块。块内再按照距离排序。

队首磁石记为 $now$ , 根据排序结果，一定存在一个整数 $k$, 满足：

• 1.第 $1\sim k-1$ 块中所有磁石质量都不大于 $now$ 的磁力。
• 2.第 $k+1$ 块之后的磁石质量都大于 $now$ 的磁力，不可能被吸引。 因为每块内已经按照距离排序，所有对 $1\sim k-1$ 块中与 $(x_0,y_0)$ 的距离小于等于 $now$ 的吸引半径，而且处于块的前段，那么直接扫描每一块，将能够吸引的磁石加入队列中，直到第一个不能被吸引的磁石的位置，记为 $p$ 。之后，对于每一块该块起点移动到 $p$，这样被吸引的磁石就不会被重复扫描。 对于每个位置均摊复杂度是 $O(1)$ , 处理 $k-1$ 时间复杂度就是 $O(\sqrt{N})$ 。

对于第 $k$ 块，可能最轻的小于 $now$ 的磁力，最重的大于 $now$ 的磁力(但是块内已经按照距离排序)，可以直接朴素扫描该块，把能够吸引的磁石取走，时间复杂度是 $O(\sqrt{N})$。

整个算法复杂度是 $O(N\sqrt{N})$

【参考代码】点击

本题双倍经验：CF198E-Gripping Story

---

其他分块练习题：

1.P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

题意：给你一个长为 $n$ 的排列，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。

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

题意：给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的逆序对数。

3.P6774[NOI2020]时代的眼泪

二维顺序对，分块+容斥。

---

学习完毕

{{ select(1) }}

• YES
• NO