根号算法
1. CF1806E
题意
给定一棵树，树上的每个节点权值给定，设为序列 \(a\)。
当 \(dep_x = dep_y\) 时，定义 \(w(x, y)=w(fa_x, fa_y)+a_xa_y,w(0,0)=0\)，\(q\) 次询问 \(w(x, y)\)。
\(n, q \le 105\)
题解
设定阈值 \(B\)，按深度分层。如果一层点的数量达不到 \(B\)，就预先处理出这些点对两两的答案。如何预处理呢，直接模拟，爬到上一个点数不足 \(B\) 的层即可。冷静分析下，设一层大小为 \(size\)，那么经过这层的次数不会超过 \(size\cdot B\)，故预处理的复杂度为 \(O(nB)\)。询问直接跳到上一个点数不足B的层，期间最多经过n/B的层，这里的复杂度为 \(qn/B\)，总的复杂度为 \(O(n \sqrt q)\)。离线后按层数从浅到深处理，空间复杂度为 \(O(n + q)\)。
根号分治的基本思路是按照某一阈值将问题划分为两部分解决。就像这道题，不一定要分别单独解决，而是可以先解决容易处理的那部分，另一部分依赖第一部分解决。
2.
题意
给定一张有向图，\(n\) 个点，\(m\) 条边，再给定 \(q\) 组询问，每次询问 \(x\) 能否到达 \(y\)。
题解
直接 \(bitset\) 即可，复杂度 \(O(\frac{mn}{\omega}+q)\)，但有一个省空间的技巧，直接 \(bitset\) 存空间大，不妨按 \(y\) 分组处理询问，
每组 \(O(\omega)\) 个，做 \(O(\frac n{\omega})\)次，空间 \(O(n)\)。
根号分治的思想可以迁移，也就是是把复杂度平均。本题是将时间复杂度和空间复杂度平均。
3. P7125
题意
给定一个长为 \(n\) 的序列 \(a\)，定义 \(x\) 为区间 \([l, r]\) 的众数当且仅当不存在 \(y\) 使得 \(y\) 在区间 \([l, r]\) 中的出现次数大于 \(x\) 在区间 \([l,r]\) 中的出现次数。
有 \(m\) 次询问，每次询问给出 \(l, r\)，求有多少二元组 \((l',r')\) 满足 \(l\le l'\le r'\le r\)，且 \([l', r']\) 的区间长度为奇数，且 \((l' + r') / 2\) 是区间 \([l', r']\) 中的众数。
\(n,m\le 5\times10^5\)
题解
令 \(c_x\) 表示 \(x\) 出现的次数，则 \(x\) 在区间 \([x-i,x+i]\) 中的出现次数可能是 \(0\dots c_x\)，最直接的想法是对每个数的没种出现次数处理，找到最多 \(c_x\) 个产生贡献的 \(i\) 的区间。复杂度是二分 \(+\) 区间众数最优 \(O(n\sqrt{n\log n})\)。
考虑根号分治，此时问题分为两步解决：
预处理：
\(c_x\le B\) 的 \(x\) 统一解决，枚举 \(x\) 的出现次数 \(k\)，对每个 \(k\)，\(O(n)\) 求出序列 \(p_i\) 表示满足区间 \([i,j]\) 的众数出现次数为 \(k\) 的最小的 \(j\)。以最开始的思路二分，用 \(p_x\) 代替区间众数判断，复杂度就变成 \(O(n\log n)\)。一共要求 \(B\) 次 \(p_x\)，复杂度 \(nB\)。
\(c_x\ge B\) 的 \(x\) 不超过 \(\frac nB\) 个，每一个可以 \(O(n)\) 求出产生贡献的 \(i\) 的区间。复杂度 \(O(\frac{n^2}B)\)。
回答询问：
现在已经求出对每个数 \(x\)，使 \([x-i,x+i]\) 产生贡献的 \(i\) 的区间，且这种区间不超过 \(n\) 个。
令对每个询问 \(mid=\lfloor\frac{l+r}2\rfloor\)，\(x\le mid\) 时 \(l\) 会限制 \(i\) 的选择，二维数点计算。\(x>mid\) 时类似。
那个 \(p\) 数组实在是太奇妙了，不知道是怎么想出来的。应该可以从第一个思路的二分判断的优化推一推。