例题
1.Remainder Problem
两种暴力
按题意模拟，修改时间复杂度 $O(1)$，查询时间复杂度 $O(n)$。
维护一个 $b$ 数组，$b_{ij}$ 表示所有模 $i$ 得 $j$ 的下标的数之和，修改时间复杂度 $O(n)$，查询时间复杂度 $O(1)$。
两种暴力时间复杂度极不平衡。考虑设计一个阈值 $B$，将询问分成两块，分别处理。对于 $\le B$ 的，用法二。对于大于 $B$ 的，用法一。
取 $B=\sqrt n$，时间复杂度 $O(q\sqrt n)$。
由于数据问题，块长取理论最优块长不一定最优。
2.Two Arithmetic Progressions
不妨设 $a_1>=a_2$。有两种暴力
枚举。时间复杂度 $O(\frac{n}{a_1})$。
循环节大小为 $lcm(a_1,a_2)$，找到第一个重复的位置 $x$，答案即为 $\left\lfloor \frac{R-x}{lcm(a_1,a_2)}\right\rfloor +1$。时间复杂度 $O(\frac{lcm(a_1,a_2)}{a_1})$。
将两个暴力拼一起，记 $B=\sqrt{2 \times 10^9} \approx 44722$。小于或等于 $\le B$ 的用法二，否则用法一。
3.[IOI2009] Regions
点染色很显然可以根号分治，然后就 $O(n\sqrt{n})$ 了。
对于都为小颜色的，我使用了虚树求解。需要大力卡常，包括但不限于
用 dfs 序求 lca。
按 dfs 序排序时用归并排序。
限制大颜色的数量，将每个颜色对应的点的个数求出，取第 $k$ 大为阈值。
邻接表换为链式前向星。
4.[ARC052D] 9
数位之和最大为 $90$。对 $K$ 分讨
$K \le \sqrt{M}$，直接枚举。
$K \le \sqrt{M}$，数位 DP。