[笔记] 根号算法

[笔记] 根号算法引子张队药学根号算法。。也不知怎样勾起了我的兴趣。。。借鉴了’\Miracle\’的思想根号算法是一种很常见的算法常见的根号思想有:双向搜索、根号分类讨论、根号重建、复杂度平衡,以及一些根号级别的数据结构如分块和莫队这些算法一般是多种暴力算法的结合,一般具有较低的思维难度和编码难度

大家好,欢迎来到IT知识分享网。

引子

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

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

根号分类讨论

(下面两道题都是跟图论有关的)

好像这个也算

一个想法

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

能量石(From *Miracle*)

[笔记] 根号算法
详见原博客

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

与模数&倍数有关的

\(x>\sqrt n\) 时,倍数只有 \(\sqrt n\) 种。
\(x\leq \sqrt n\) 时,模意义下不同的数只有 \(\sqrt n\) 种。

街灯

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

对于每个询问,我们根据 \(p\) 的大小分类讨论。
考虑如何平衡修改与查询的复杂度,我们可以每次花 \(O(100)\) 处理出一个数对 \(p\leq 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

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/34704.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信