暴力美学的集大成体现。

  1. 通常是对同一个问题有两种暴力的方法分别适用不同的数据范围，那么可以以某一个值为分界点，当小于这个阈值用一种暴力 $O(b)$，大于就用另一种暴力 $O(\frac{n}{b})$；
  2. 这个值通常为 $\sqrt{N}$ ；
  3. 这类题目会有明显或隐藏的限制条件，比如某个值的数量一定。

例1

给一个长为 $5\times 10^5$ 的序列，初值为0，完成 $q$ 次操作，要么是将 $a[x]$ 加上 $y$ ，要么是询问所有下标模 $x$ 等于 $y$ 的位置之和。

设置阈值 $b$ ，对于小于 $b$ 的模数，预处理数组 $dp[i][j]$ 表示模 $i$ 余 $j$ 的所有下标的数之和。

  1. 若模数大于 $b$ ，直接暴力枚举，$O(\frac{n}{b})$。
  2. 若模数小于 $b$ ，使用预处理的数组 $O(1)$ 查询。
  3. 对于更改，只修改模值小于 $b$ 的 $dp[i][j]$ ，$O(b)$。

故总时间复杂度为 $O(q(b+\frac{n}{b}))$ ，使阈值 $b=\sqrt{n}$ 时复杂度最低。

例2

$n$ 位用户组成了一个双向的网络。如果第 $i$ 个用户向他的好友 $j$ 分享了一张照片，那么， $j$ 的所有好友包括他自己就能看到这张照片。现在，用户 $u$ 想分享一张照片，但是TA不想让 $v$ 看到这张照片。在不发送给自己的情况下，TA想知道，他最多可以发送给多少位好友？ $1\leq n,q\leq2\times 10^5,1\leq m\leq7\times10^5$

有两种明显的暴力：

  1. 暴力枚举 $u$ 的所有邻居并用 $map$ 判断其是否是 $v$ 的邻居。$O(nlogn)$ 。
  2. 在每个点处开一个 $bitset$ 维护与它相连的点的序列，答案即为 $b_u\oplus(b_u\ and\ b_v)$ 中1的数量。$O(\frac{n}{w})$ 。

但是法1时间会爆，法2空间会爆。注意到所有点的度为 $2m$ ，那么可以设定阈值 $K$ 表示一个点的度，根据每个点的度将其分为重点和轻点：

  1. $u$ 重 $v$ 重：用法2.
  2. $u$ 重 $v$ 轻：枚举 $v$ 的邻居，判断其是否在 $u$ 的 $bitset$ 中。
  3. $u$ 轻 $v$ 重：枚举 $u$ 的邻居。判断其是否在 $v$ 的 $bitset$ 中。
  4. $u$ 轻 $v$ 轻：枚举 $u$ 的邻居。判断是否在 $map$ 中。