腾飞计划寒假第五课——根号分治&分块 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)$。

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

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

设阈值 $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)$。

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

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

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

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

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

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

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

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

非常简单？0pts 求条。

小势能线段树。

小红题。

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

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

条件：

构造方法：

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

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

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})$。