腾飞计划寒假第五课——根号分治&分块 2025/2/6

· · 个人记录

根号分治

设一个阈值 B，如果查询数值 m\le B 就用一种方法处理（时间复杂度通常是约 O( n\times m)），如果 m>B 就用另一种方法处理（时间复杂度通常是 \displaystyle O(\frac{n^2}{m})），发现 B 取 \sqrt n 时最优，总体复杂度 O(n\sqrt n)。

实际上是一种平衡复杂度的暴力算法。

P11287 [COTS 2017] 影响 Utjecaj

把把关键点挖了找连通块，把一个连通块缩成一个点，权值是连通块的大小。

设阈值 B，若点的度数小于 B，暴力找即可。否则设 ans_x 表示度数第 x 大的答案，每次更新逐个更改。

没找到的题：

序列 a，每次给个 x 和 y，查询最小的 |i-j| 使得 a_i=x,a_j=y。

设阈值 B，如果 x 和 y 的出现次数小于 B，双指针暴力即可。

如果其中一个大于 B，预处理 ans_{x,y}（x\in[1,\sqrt n],y\in[1,n]），表示「出现次数大于 B 的第 x 大的值」和第 y 个值的最小距离。

枚举 i，ans_{x,a_i}=\min(ans_{x,a_i},|i-j|,|k-i|)，j 和 k 是值为 x 的两个位置。

因为出现次数大于 \sqrt n 的最多 \sqrt n 个，所以时间复杂度是 O(n\sqrt n)。

P5901 [IOI 2009] Regions

设属于 r1 的为红点，属于 r2 的为绿点。处理树的 dfs 序，将区间差分成前缀，双指针处理出红点之间的绿点个数。双指针一个指红点，一个指绿点，只要指的绿点在指的红点左边，就往后找绿点，否则找下一个红点。

如果红点和绿点个数均小于 B，用以上类似的双指针查询即可。

如果 r1>B，预处理 ans1_{x,y} 表示 y 到根节点有多少个出现次数第 x 多的点。

如果 r2>B，预处理 ans2_{x,y} 表示 y 的子树中有多少个出现次数第 x 多的点。

P9809 [SHOI2006] 作业 Homework

当 y<B 暴力去找，否则二分比 y 大的下一个，比 y\times2 大的下一个，比 y\times3 大的下一个，……，时间复杂度 O(\displaystyle\frac{n^2}{B}\log n)。

P4109 [HEOI2015] 定价

唐诗做法，分块打表，以 10^7 为一个块，整块预处理，散块暴力。

P3203 [HNOI2010] 弹飞绵羊

不带修可以预处理，将序列分成根号块，维护下一步跳出本块的那一步跳到哪个块距离多少。

每次修改只影响本块内的值，对该块重构即可。

P8572 [JRKSJ R6] Eltaw

非常简单？0pts 求条。

CF920F SUM and REPLACE

小势能线段树。

P7446 [Ynoi2007] rfplca

小红题。

类似弹飞绵羊，维护每个点往前跳出这个块的第一步，查询时整块就往前跳，如果跳到了一起，可能在此之前就到 LCA 了，暴力往后找，每次查询 \sqrt n。

一个块被修改 \sqrt n 次之后就一定一步能跳出块，一个块修改的前 \sqrt n 次和散块暴力重构，\sqrt n 个块，最多修改 \sqrt n 次，每次修改时间复杂度 \sqrt n，总体复杂度 O(n\sqrt n)。

树分块

条件：

  1. 属于同一块的节点之间的距离步超过给定块的大小
  2. 每个块中的节点不能太多也不能太少
  3. 每个节点都要属于一个块
  4. 编号相邻的块之间的距离不能太大

构造方法：

dfs，并创建一个栈，dfs 一个点时先记录初始栈顶高度，每 dfs 完当前节点的一棵子树就判断栈内的数量是否大于等于 B，时则将栈内所有新增点分为同一块，核心点为当前 dfs 的点，当前节点结束 dfs 时将当前节点入栈，整个 dfs 结束后将栈内所有剩余节点放到最后一个块。

除了最后一个块，其余块的大小都在 [B,2B-1] 之间，最后一个块的大小在 [0,3B-2] 之间。

P6177 Count on a tree II/【模板】树分块

bitset 每一位表示颜色 i 是否出现过，将两段路径或起来就是两端路径一共的值。

选一个深度最深的点，找到它的 B 级祖先的子树删掉，树变成 \sqrt n 个块。

随神的是 \sqrt n 倍数并且向下最深深度大于等于 \sqrt n 的点来打关键点，会有 \sqrt n 个关键点，从每个点向上的长度也是 \sqrt n。

预处理两两之间的答案，用 bitset 存储。每个关键点与离他最近的关键点统计答案，预处理时间复杂度 O(\frac{n\sqrt n\times\sqrt n}{64})=\displaystyle O(\frac{n^2}{64})。

然后询问就变成里一个点到关键点加另一个关键点到另一个点，询问复杂度 O(\displaystyle\frac{m\sqrt n+n\times m}{64})。