根号平衡
泛化ψ(｀∇´)ψ
也被广泛叫做根号分治。
具体来说，当你发现暴力的实际基本操作数随着一些信息而变化，并且这些信息存在一个恒定的上界。
我们可以考虑两个不同的暴力，分别在不同的极端情况下具有优势，然后设定一个阈值 \(B\)，按照信息和阈值的关系分别使用两种不同的暴力。
通常 \(B\) 都取根号，所以叫做根号平衡。
因为我们通常分析时间复杂度的时候更关心的是最坏/均摊复杂度，我们会忽略掉因为一些信息导致实际操作数的变化。
根号平衡就是通过取每种暴力实际操作数尽量小的情况，拼凑起来。
CF1207F Remainder Problemψ(｀∇´)ψ
给你一个长度为 \(500000\) 的序列，初值为 \(0\) ，你要完成 \(q\) 次操作，操作有如下两种：
1 x y: 将下标为 \(x\) 的位置的值加上 \(y\)2 x y: 询问所有下标模 \(x\) 的结果为 \(y\) 的位置的值之和
一种直观的暴力就是，每次 \(O(1)\) 单点加，然后 \(O(n / x)\) 的询问（实际上均摊复杂度还是 \(O(n)\)），空间复杂度为 \(O(n)\)
另一种暴力是反过来，维护一个 \(n \times n\) 的矩阵，\((i, j)\) 表示模 \(i\) 为 \(j\) 的值的和，空间复杂度为 \(O(n^2)\)。
于是每次更新就要更新 \(O(n)\) 个值（实际上是更新 \(O(x)\) 个），但是查询就是 \(O(1)\) 了。
可以发现这两个做法是两个极端，我们有没有办法像一些 \(\log\) 数据结构一样，通过平衡形如差分前缀和这样复杂度呈对称的算法，达到更优的均摊复杂度呢？
答案是肯定的，我们观察一下 \(O(n / x)\) 这个东西，当 \(x\) 越大的时候，它的实际基本操作数就越少。
而后面这个暴力，当 \(x\) 越小的时候，更新所消耗的基本操作数就越小。
所以我们不妨考虑一个类似分开处理的东西，设定一个阈值 \(B\)，如果 \(x \ge B\)，那么我们就选择第一种暴力，否则选择第二种暴力。
这样的复杂度是 \(O(q(B + \dfrac{n}{B}))\) 的，取 \(B = \sqrt n\) 可以做到 \(O(q\sqrt n)\)，空间复杂度为 \(O(n)\)
实际实现就是修改的时候两边都修改，但是暴力二只修改小于 \(\sqrt n\) 的部分，然后查询的时候对于小于 \(B\) 的部分直接输出，否则暴力跳。
暴力一显然需要把对整个序列的操作都弄完，所以修改的时候不能只选取暴力二。
CF710D Two Arithmetic Progressionsψ(｀∇´)ψ
已知两个无限长的等差数列，首项分别为 \(b_1, b_2\)，公差分别为 \(a_1, a_2\)，求 \([L,R]\) 中有多少个数在两个等差数列中都出现了。
值域正负 \(2e9\)，但是 \(a, L, R\) 非负。
考虑一个暴力，枚举第一个等差数列里在 \([L, R]\) 中的数，判断是否在第二个等差数列里面。
这个暴力的复杂度为 \(O(\dfrac{R - L}{\max(a_1, a_2)})\)。
考虑另一个暴力。
可以发现要求的所有数存在循环节，循环节为 \(\operatorname{lcm}(a_1, a_2)\)。
尝试找到第一个重合的数，然后找出有多少个循环节就行，这部分复杂度为 \(O(a_1a_2)\)
考虑平衡，设定一个阈值 \(B\)，如果 \(\max(a_1,a_2) \ge B\)，选择第一种暴力，否则选择第二种暴力。
于是复杂度可以变成 \(O(\dfrac{2e9}{B} + B^2)\)，然后发现 \(B = 1e3\) 左右比较合适。
Luogu8250 交友问题ψ(｀∇´)ψ
洛谷上有 \(n\) 位用户，这些用户组成了一个双向的网络。
洛谷的图片分享机制如下：如果第 \(i\) 个用户向他的好友 \(j\) 分享了一张照片，那么，\(j\) 的所有好友 \(k\) 就能看到这张照片。\(j\) 也可以看到这张照片。
现在，用户 \(u_i\) 想分享一张照片，但是TA不想让用户 \(v_i\) 看到这张照片。在不发送给自己的情况下，TA想知道，他最多可以发送给多少位好友？
\(1 \le n,q \le 2\times10^5\)，\(1\le m \le 7\times 10^5\)。
保证没有重边和自环
考虑一个暴力，对每个节点存一个 bitset，直接枚举邻域按位操作就行，时空复杂度均为 \(O(n^2/\omega)\)。
考虑另一个暴力，存下每条边，枚举邻域，看看邻域的邻域当中有没有 \(v\) 出现，复杂度 \(O(n\log n)\)，空间复杂度 \(O(n^2\log n)\)。
但注意到一个事情，一张无向图的度数恒为 \(2m\)，而这两类暴力的实际操作数以及空间复杂度都和节点度数相关
我们可以考虑把节点分成两类，一类是度数不大于 \(B\) 的，称作轻点，另一类为重点。
考虑分四种情况讨论，也就是讨论 \(u,v\) 的轻重情况。
然后我们发现重点不超过 \(n / B\) 个，轻点度数又不大于 \(B\)，所以可以通过调整 \(B\)，最终做到 \(O(n\sqrt{\dfrac{n\log n}{\omega}})\) 的时空复杂度。
这种思想在三/四元环计数里也用到了。