简介
大概是对根号算法的总结吧，大概
强制在线，只有询问
对于这种题目，分块算法一般的思想是预处理出块 $i$ 到块 $j$ 的答案，边角中间的块对边角的影响用其它数据结构来存储
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次询问，每次询问区间 $[l,r]$ 的众数，强制在线
$n \le 4\times 10^4,m\le 5 \times 10^5$
简要题解：由于没有修改，我们可以预处理块 $i$ 到块 $j$ 的众数，边角的数只有 $O(\sqrt n)$，对于这些数我们只需要暴力判断即可，时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n\sqrt n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次询问，每次询问区间 $[l,r]$ 的逆序对个数
$n,m \le 5\times 10^5$
简要题解：我们考虑预处理块 $i$ 到块 $j$ 之间的答案，边角拿主席树暴力处理
时间复杂度 $O(n\sqrt n\log n)$，可以通过增加码量来优化掉 $\log$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定 $l,r,v$，然后我们从 $a_l$ 开始到 $a_r$，每次将 $v$ 置成 $|v-a_l|$，求最终 $v$ 的值
$n,m\le 10^5$
简要题解：我们考虑分块，对于每一块求出进入这块之前的值为 $v$ 时，离开这块的值是多少，这样我们询问的复杂度就是 $O(\sqrt n)$，我们考虑如何预处理这个东西
注意到一开始这个东西是一个 $y=x$ 的函数，每有一个 $a_i$，都相当于将其从某个点对折，这样是一个对称，我们可以用并查集来维护取值相同的位置
具体的，我们存储当前直线 $x=ky+b$ 以及 $x$ 的范围 $[l,r]$，对于一条 $y=a$ 的直线，我们求其与直线交点的横坐标 $x_0=ka+b$，根据这个我们来缩短 $l,r$ 以及求新的 $k,b$，时间复杂度 $O(n\sqrt n\alpha(a))$
2021 Hubei Provincial Collegiate Programming Contest K Chtholly and World-End Battle
由只有询问的题目拓展到包含修改
这类题目一般在只有询问时可以做到提前处理好答案数组，这时候分块的作用就是使得在修改的时候可以在块内进行重构
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，从点 $i$ 出发会被弹到 $i+a_i$，接着从 $i+a_i$ 弹到 $i+a_i+a_{i+a_i}$，直至弹到大于 $n$ 为止，每次操作修改一个 $a_i$，或者询问从 $i$ 开始需要多少步弹飞
$n\le 2 \times 10^5,m\le 10^5$
简要题解：对于每个块预处理 $d_i$ 表示从 $i$ 开始被弹飞的次数，修改直接重构，时间复杂度 $O(n\sqrt n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，第一种操作修改一个 $a_i$ 的值，另一种操作给定 $k$ 和 $x$，求 $\sum_{i=1}^n[i\equiv x(\bmod k)]a_i$
$n,m\le 1.5\times 10^5$
简要题解：注意到当模数大于 $\sqrt n$ 时可以直接暴力
所以我们只需要存储模数小于 $\sqrt n$ 的答案，预处理的复杂度为 $O(n\sqrt n)$
修改时我们也只需要考虑改完之后对于模数小于 $\sqrt n$ 的答案的影响，可以直接暴力修改，复杂度是 $O(\sqrt n)$
对操作序列分块
这类题目大概就是对于根号个修改一同处理它们对询问的贡献，对于每个询问块内的修改暴力算，块外的之前已经预处理好了
简要题意：给定一棵大小为 $n$ 的树，初始时一号节点被染黑，其余节点都是白色，每次操作染黑一个节点，或者查询点 $u$ 到最近黑点的距离
$n,m\le 10^5$
简要题解：
对操作序列分块
对于若干次将点染成红色，我们可以将其放到一起做多源 $bfs$ 从而得到它们对其他点的贡献
对于一次询问，块内的染色暴力，块外的在之前已经与处理好了，时间复杂度 $O(n\sqrt n)$
简要题意：给定一个长度为 $n$ 字符串 $S$，现在有 $m$ 次操作，操作有三种，第一种操作是在 $S$ 的末尾插入一个字符 $ch$；第二种操作是删除 $S$ 的第一个字符；第三种操作是给定一个字符串 $T$，求 $T$ 在 $S$ 中的出现次数
$n,m\le 10^5,\sum |T|\le 5\times 10^6$
简要题解：我们考虑对操作序列分块，每 $B$ 次操作重构一次，两次重构之间的操作我们维护原串的 $hash$ 值枚举起点和终点暴力判断即可，时间复杂度 $O(26\frac{n}{B}n+nB)$，取 $B$ 为略大于 $\sqrt n$ 的时候跑得最快
分块优化暴力
简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，第 $i$ 条边的边权为 $(a_i,b_i)$，现在有 $q$ 次询问，每次询问给定 $u,v,a,b$，问是否存在一条从 $u$ 到 $v$ 的路径满足路径上所有边的 $a_i\le a,b_i\le b$ 且满足 $max a_i=a,max b_i=b$
$n,q\le 5\times 10^4,m\le 10^5$
简要题解：我们考虑首先将边按照 $a$ 排序后分块，那么每个询问所对应的边都是一个前缀，这个前缀包含了一些整块和一个散块，我们将这个询问放进这个散块中，同时每个散块中的边按照 $b$ 排序
然后我们直接暴力，我们枚举块，然后将这个块之前所有块内的边按照 $b$ 排序，然后我们枚举当前块内的询问，询问已经按照 $b$ 排好序，那么对于前面所有整块的内的边和询问是一个双指针的过程，而散块内的边我们暴力加入即可
维护边使用带撤销并查集即可，取块大小为 $\sqrt {n\log n}$ 可以得到时间复杂度为 $O(n\sqrt {n\log n})$
更加一般的数据结构题目
这类题目的思想类似于线段树，只不过有些东西线段树没法维护，所以只能用分块来操作
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，每次操作对 $[l,r]$ 内的 $a_i$ 区间加，或者查询区间 $[l,r]$ 有多少 $a_i$ 大于等于给定数字 $v$
$n\le 10^6,m\le 3000$
简要题解：每个块内直接排序，对于修改，整块直接打标记记录，因为整块加不影响内部顺序
边角直接修改原数组，然后整个块重新排序，复杂度为$O(\sqrt nlog\sqrt n)$
对于查询，整块直接二分，边角暴力即可，复杂度为$O(\sqrt nlog\sqrt n)$，总时间复杂度为$O(m\sqrt nlog\sqrt n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，每次操作将区间 $[l,r]$ 的数字循环右移，$a[r]$ 移动到 $l$，或者给定 $l,r,k$ 查询区间 $[l,r]$ 的 $k$ 的出现次数
$n,m\le 10^5$
简要题解：注意到操作的本质就是双端队列扔掉队尾，然后 $push$ 到队首
我们考虑分块，每个块维护一个 $deque$ 和块内某个值的个数，修改和查询都是 $O(\sqrt n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $k$，要求将序列划分长若干段，且每段中恰好出现一次的数的个数不超过 $k$，求所有划分方法，对 $998244353$ 取模
$n\le 10^5$
简要题解：令 $f[i]$ 表示划分成了多少段，每次新加入一个数，将会使 $[pre_i+1,i]$ 区间加 $1$，$[pre_{pre_i}+1, pre_i]$ 区间减一
容易转换题面为每次区间加一或减一，求权值小于等于 $k$ 的位置的 $f$ 的和
考虑分块维护，每个块维护权值为 $s,s\in[1,n]$ 的 $f$ 的和，由于每次修改只有加减 $1$，所以可以做到每次修改 $O(1)$ 维护全局答案，时间复杂度 $O(n\sqrt n)$
简要题意：给定 $n$ 个数 $a_i$，现在有 $m$ 个操作，操作有三种，第一种是区间查询最大值，第二种是交换两个数的位置，第三种是区间加等差数列
$n,m\le 10^5$
简要题解：我们考虑分块维护这个东西，对于区间加等差数列，我们将每个点看做 $a_i+d_{bl_i}\times i+add_{bl_i}$，其中 $bl_i$ 表示这个点所属块，容易发现对于一个块，可以 $O(\sqrt n)$ 修改，我们考虑如何维护区间最值
我们将每个点的式子写出来 $t=a_i+d\times i$，我们移项得到 $a_i=(-d)\times i+t$，我们令 $y=a_i,k=-d,x=i,b=t$ 我们需要求 $t$ 最大，现在我们已知 $x$ 和 $y$，那么我们直接考虑每个块内维护上凸壳，那么这样看起来对于一个快我们的询问是 $O(\log n)$ 的，我们考虑这样优化，注意到区间加等差数列的值永远是正的，那么容易得到每个区间的斜率是递减的，也就是说取值最大的点是向右的，我们维护这么一个指针即可
每次区间加和二操作，我们直接重构块即可，时间复杂度 $O(n\sqrt n)$
根号分治
根号分治更多的时候是指一种思想，具体实现则可以使用多种数据结构进行辅助
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，第一种操作修改一个 $a_i$ 的值，另一种操作给定 $k$ 和 $x$，求 $\sum_{i=1}^n[i\equiv x(\bmod k)]a_i$
$n,m\le 1.5\times 10^5$
简要题解：我们考虑对于模数是否大于 $\sqrt n$ 进行处理
注意到当模数大于 $\sqrt n$ 时可以直接暴力
所以我们只需要存储模数小于 $\sqrt n$ 的答案，预处理的复杂度为 $O(n\sqrt n)$
修改时我们也只需要考虑改完之后对于模数小于 $\sqrt n$ 的答案的影响，可以直接暴力修改，复杂度是 $O(\sqrt n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求最长的一个区间 $[l,r]$ 满足这个区间的众数不唯一
$n\le 2\times 10^5$
简要题解：首先有一个比较显然的性质，整个序列的众数一定是答案区间的众数之一
我们考虑根号分治，不妨设整个序列的众数为 $p$
对于出现次数大于 $\sqrt n$ 的数 $v$，这些数的个数不会超过 $\sqrt n$ 个
我们对于每个 $v$，把出现一个 $v$ 当做加一，出现 $p$ 当做减一，然后通过前缀和对于一个 $v$ 可以 $O(n)$ 统计答案
注意到可能有一个小问题就是可能统计的区间中出现次数最多的数并不是 $p$ 和枚举到的 $v$
如果是这样的话，这个区间一定能变得更大，所以不会影响答案
对于出现次数小于 $\sqrt n$ 的数，我们直接枚举答案区间的众数的出现次数 $k$，然后对于每个 $k$，如果固定左端点，则最远的合法右端点是一个定值，且随着左端点的增加而增加，所以可以直接双指针
总的时间复杂度为 $O(n\sqrt n)$
简要题意：给定一个长度为 $n$ 的字符串 $s$，现在对于 $k\in[1,n]$，求将 $s$ 分成 $m=\lfloor\frac{n}{k}\rfloor$ 段，每段长度为 $k$，第 $i$ 段的起点为 $(i-1)\times k+1$，定义 $f(k)=\sum_{1\le i <j\le m}[dist(p_i,p_j)\le 1]$，其中 $p_i$ 表示第 $i$ 段，$dist$ 表示两个串的汉明距离
$n\le 2\times 10^5$
简要题解：我们考虑根号分治，将 $k$ 按照 $\sqrt n$ 进行分治
对于 $k<\sqrt n$，我们考虑 $O(n)$ 解决，我们计算每个串的每个位置变成 $?$ 的 $hash$ 值并进行计算，如果两个串恰有一个位置不同那么我们不会算重，如果两个串完全相同，那么我们会算 $k+1$ 次，稍微处理一下即可
对于 $k>\sqrt n$，我们直接枚举所有 $(i,j)$ 然后用后缀数组判一下 $lcp$ 和 $lcs$ 长度之和是否大于等于 $k-1$ 即可，枚举 $(i,j)$ 的复杂度为 $\frac{n^2}{k^2}$，$O(\sum_{k=\sqrt n}\frac{n^2}{k^2})=O(n\sqrt n)$
因为前半部分查找 $hash$ 值速度较慢，所以我们我们后半部分多做一点即可
2019-2020 Winter Petrozavodsk Camp, Day 8: Almost Algorithmic Contest B String Algorithm
简要题意：给定一个长度为 $n$ 的排列 $p_i$，现在有 $m$ 次操作，操作有两种，第一种给定 $x$ 和 $y$，交换 $p_x$ 和 $p_y$，第二种给定 $i$ 和 $k$，求执行 $i=p_i$操作 $k$ 次之后，$i$ 的值
$n,m,k\le 10^5$
简要题意：考虑根号分治，我们对于每个点维护跳 $O(\sqrt n)$ 次到达的位置，这样在交换 $p_x$ 和 $p_y$ 时候，需要修改的点只有 $O(\sqrt n)$ 个，查询我们也只需要跳 $O(\sqrt n)$ 步
简要题意：给定一个长度为 $n$ 的序列 $a_i$，每次操作可以选择一个 $i$ 将 $a_i$ 变成任意一个整数，求最小需要多少次操作可以整个序列变成一个等差数列
$n,a_i\le 10^5$
简要题解：注意到 $a_i\le 10^5$，也就是说公差一定是 $10^5$ 范围内，另外如果公差为 $d$，那么可能可以保留的子区间的长度就是 $\frac{10^5}{d}$，容易想到根号分治
枚举公差 $d$，如果公差小于 $\sqrt n$，那么我们直接暴力整个序列 $a_i$，将 $a_i$ 减掉 $i\times d$，相同大小的数的个数的最大值即为可以保留的数，时间复杂度 $O(n\sqrt n)$
如果公差大于 $\sqrt n$，我们知道子区间的长度一定小于 $\sqrt n$，所以我们枚举所有长度为 $\sqrt n$ 的子区间，我们认为一定保留区间左端点 $a_l$，那么对于一个 $a_i$，如果 $a_i-a_l$ 能够被 $i - l$ 整除的话，那么对于公差 $\frac{a_i-a_l}{i-l}$，$a_i$ 才能被保留，我们把 $a_i$ 贡献到这个公差上即可，这里的时间复杂度就是 $O(n\sqrt n)$，总时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n\sqrt n)$
简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，每个点有点权 $a_i$，现在有 $q$ 个操作，操作有两种，第一种操作给定 $x$ 和 $y$，修改 $a_x=y$；第二种操作给定 $x$，求与 $x$ 有连边的所有点 $a_y$ 所形成的的集合 $S$ 的 $mex$ 是多少
$n,m,q\le 10^5$
简要题解：因为所有点的总点数为 $2n$，所以我们按照点的度数进行根号分治，以 $B$ 为分界线，度数小于等于 $B$ 的称为小点，度数大于 $B$ 的称为大点
对于小点的查询，我们直接暴力即可，时间复杂度为 $O(B)$
对于大点的查询，我们对每个大点维护一个树状数组，查询 $mex$ 可以在树状数组上二分，同时修改一个点的点权我们只需要修改这个点周围所有大点的树状数组即可，注意到一个点周围最多只有 $\frac{n}{B}$ 个大点，所有这一部分的时间复杂度为 $O(\frac{n}{B}\log n)$
总时间复杂度为 $O(B+\frac{n}{B}\log n)$，树状数组常数很小，可以通过此题
自然根号
有若干数的和为 $n$，则不同的数最多有 $\sqrt n$ 个
证明：最差情况即为 $1+2+\cdots +\sqrt n$
$\sum_{i=1}^m a_i=n$，现在有 $O(n)$ 个二元组，每个二元组 $(x,y)$ 的代价是 $O(min(a_x,a_y))$，那么总代价是 $O(n\sqrt n)$
证明：不妨令 $min(a_x,a_y)$ 为 $B$
对于 $B>\sqrt n$ 的情况，一个 $B$ 的代价最多为 $O(\frac n B)$，且一共只有 $O(\sqrt n)$ 种 $B$，这一部分的代价为 $O(n\sqrt n)$
对于 $B<\sqrt n$ 的情况，因为只有 $O(n)$ 个二元组，所以总代价也为 $O(n\sqrt n)$
简要题意：给定一棵 $n$ 个点有根树，树上每个点有一个颜色 $col_i$，现在有 $m$ 个询问，每次询问给定两个颜色 $(x,y)$，问有多少对节点 $(u,v)$ 满足 $u$ 是 $v$ 的祖先且 $u$ 的颜色是 $x$，$v$ 的颜色是 $y$
$n\le 2\times 10^5,m\le 2\times 10^5$
注意到询问满足对二元组的自然根号
那么我们现在可以枚举颜色数较小的那种颜色，如果其为 $u$，那么相当于查询子树中某种颜色的个数，如果其为 $v$，相当于查询树链上的某种颜色的个数，两者皆可在 $dfs$ 的时候处理，时间复杂度 $O(n\sqrt n)$
简要题意：给定一个森林和 $q$ 个询问，每次询问给定一个无序二元组 $(x,y)$，问将 $x$ 和 $y$ 所在的树随机连接起来后的直径的期望
$n,q\le 10^5$
简要题解：首先我们对于每棵树求出树上从所有点出发的最长路径，这个有经典的 $O(n)$ 做法
那么答案即为 $\frac{1}{nm}\sum_{i=1}^n\sum_{j=1}^m max\lbrace f_{1,i}+f_{2,j},d_1,d_2\rbrace$
注意到询问满足对二元组的自然根号
所以我们枚举较小的树上的点，然后二分即可，时间复杂度 $O(n\sqrt n\log n)$
$AC$ 自动机和广义后缀自动机中用于构造该自动机的所有串的所有前缀节点的树链的并的长度和是 $O(n\sqrt n)$ 的
证明：
对于每个串 $S$，其贡献的复杂度是 $O(min(|S|^2,n))$ 的
如果 $|S|>\sqrt n$，这样的串只有 $O(\sqrt n)$ 个，每个的复杂度是 $O(n)$，总的时间复杂度就是 $O(n\sqrt n)$
如果 $|S|<\sqrt n$，其复杂度为 $O(|S|^2)$，容易得到 $O(\sum |S|^2)\le O(\sqrt n \sum |S|)=O(n\sqrt n)$
构造方法：Itst : 广义 SAM 上每个模板串包含的节点数量和的上界以及构造
简要题意：给定 $n$ 个只有 $01$ 的字符串以及 $m$ 次询问，每次询问 $[l,r]$ 的所有字符串的最长公共子串的长度
$n\le 2\times 10^4,m\le 10^5,L\le 4\times 10^5$
简要题解：首先对于所有字符串构建广义后缀自动机
然后我们考虑离线后扫描线来求解询问，我们考虑右端点 $r$ 增加时的影响
我们将广义后缀自动机上所有属于字符串 $r$ 的子串的节点拿出来，注意到这是一个自然根号，节点总数为 $O(L\sqrt L)$
我们对于每个节点维护它向左最长连续到哪里，这样每次可以 $O(1)$ 维护
然后我们考虑如何回答询问，相当于有 $O(L\sqrt L)$ 次单点修改，$O(m)$ 次区间查询最大值，这个东西我们再做一次根号平衡，总的时间复杂度为 $O(L\sqrt L+m\sqrt n)$
根号平衡
不同种类的操作的个数不同的情况下来保证复杂度
区间查询 单点修改
如果总的操作个数是 $O(n)$ 的话，显然最优的方法是树状数组，可以做到 $O(n\log n)$
如果操作个数不平均呢 ？
假设修改有 $O(n)$ 个，而查询有 $O(n\sqrt n)$ 个
如果使用树状数组的话，复杂度是 $O(n\sqrt n\log n)$ 的，显然不优
这时候我们考虑分块维护前缀和
1
2
3
4
5
6
7
8void add(int x, int v) {
for (int i = x; i <= r[bl[x]]; ++i) a[i] += v;
for (int i = bl[x] + 1; i <= num; ++i) d[i] += v;
}
inline int get_sum(int x) {
return a[x] + d[bl[x]];
}那么如果修改 $O(n\sqrt n)$ ，查询 $O(n)$ 呢
同样是分块，直接维护单点和即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16inline void add(int x, int v) {
a[x] += v; d[bl[x]] += v;
}
int query(int L, int R) {
int s = 0;
if (bl[L] == bl[R]) {
for (int i = L; i <= R; ++i) s += a[i];
return s;
}
for (int i = L; i <= r[bl[L]]; ++i) s += a[i];
for (int i = l[bl[R]]; i <= R; ++i) s += a[i];
for (int i = bl[L] + 1; i < bl[R]; ++i) s += d[i];
return s;
}区间修改 单点查询
维护差分数组就可以转换为上面的情况
插入一个数，查询小于一个数的个数
不妨设插入的总数和数的大小都是 $O(n)$ 的
要求插入 $O(\sqrt n)$，查询 $O(1)$
值域分块，维护前缀和即可
1
2
3
4
5
6
7inline void add(int x, int v) {
int B = bl[x];
for (int i = B + 1; i <= num; ++i) d[i] += v;
for (int i = x; i <= r[B]; ++i) pre[i] += v;
}
inline int query(int x) { --x; return d[bl[x]] + pre[x]; }