[笔记] 根号算法

引子

张队药学根号算法。。也不知怎样勾起了我的兴趣。。。
借鉴了 *Miracle* 的思想

根号算法是一种很常见的算法
常见的根号思想有：双向搜索、根号分类讨论、根号重建、复杂度平衡，以及一些根号级别的数据结构如分块和莫队
这些算法一般是多种暴力算法的结合，一般具有较低的思维难度和编码难度
——ImmortalCO猫

根号分类讨论

（下面两道题都是跟图论有关的）

好像这个也算

一个想法

（From the_Death的课件）
当时说随机数据是 (nsqrt n) 的，现在想想好像也可以做到稳定 (nsqrt n)。
我们按点的度数对点分类，若点 (u) 的度数 (d[u]>sqrt n) ，称为大点；反之称为小点。
我们预处理出与每个点相连的大点的集合 (S(u)) ,显然 (forall u,|S(u)|<=sqrt n)
然后对于每个点维护两部分答案：一部分是与每个点相连的小点的答案，另一部分我们暴力统计 (vin S(u)) ，每个 (v) 的状态。
修改时，如果 (u) 是一个小点，我们修改与他相连的所有点即可；如果他是一个大点，我们只修改他的状态即可。

能量石（From *Miracle*）

详见原博客

下面的两个部分其实都是平衡复杂度。

与模数&倍数有关的

当 (x>sqrt n) 时，倍数只有 (sqrt n) 种。
当 (xleq sqrt n) 时，模意义下不同的数只有 (sqrt n) 种。

街灯

每个街灯上都有一个数，每次询问，第 (l) 个街灯到第 (r) 个街灯上的数模 (p) 等于 (v) 的有几个。
(1≤N,M≤10^5) ,街灯上的数不超过 (10^4) , (1≤p≤10^9)。

对于每个询问，我们根据 (p) 的大小分类讨论。
考虑如何平衡修改与查询的复杂度，我们可以每次花 (O(100)) 处理出一个数对 (pleq 100)时的答案，查询时直接使用答案。
当 (p > 100) ，他的倍数很少，我们可以直接查 (k*p+v) 出现了几次（之前开个桶）。

还是一个想法

给你一个集合，边往里面插数，边查询集合中大于某个数 (x) 的数的数量。
三种数据范围：
1.插入较多 (5e7) ，查询较少 (1e5)。
2.插入中等 (1e6) ，查询中等 (1e6)。
3.插入较少 (1e5) ，查询较多 (5e7)。
值域 (1e6)

我们对于 2 ，直接树状数组即可QwQ。
我们对于 1 3 ，可以分块。
我们都是维护块内前缀和，然后在维护一个块间前缀和。
对于 1 ，我们可以 (O(1)) 插入，修改所属块和对应的桶即可， (O(sqrt n))查询。
对于 3 , 我们可以 (O(sqrt n)) 插入，修改所属块，对应的桶，并计算前缀和，(O(1)) 查询。

跟集合有关的运算

我们定义 (f[A][B]) 为 二进制表示下 前8位位(A) 的子集，后8位为 (B) 的数的个数。
添加时枚举超集，查询时枚举子集。

2019.11.20 coming back