大家好,欢迎来到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