根号算法题库"/>

根号算法题库

前言

根号算法博大精深，决定在此收集。
例题我博客基本都能找到。

带根号算法

分块算法

一种是最普通的分块算法，把序列分块，然后可以解决区间问题。分块算法可以维护一些线段树维护不了的东西，例如单调队列等，线段树能维护的东西必须能够进行信息合并，而分块则不需要。不过，和线段树一样，分块需要支持类似标记合并的东西。
当然，为了使得速度不至于太慢，每一块的大小应该通过实验得知。即找到一个合理的块大小，使得在该大小下算法跑的比较快。
具体实现时，用belong[i]表示i所属块。对于修改操作，某一块全部要被修改，则更改它的信息。多余部分直接暴力修改，有些时候需要对多余部分所属块进行暴力重构（例如维护单调队列）。
例题：jzoj3167查税，用分块维护单调队列。去年五校联考第六场的第三题，用分块维护桶。bzoj2002弹飞绵羊，用分块维护答案。bzoj3809Gty的二逼妹子序列的一种算法中需要用到这种最普通的分块。jzoj4438K小数查询。

还有其他的分块，这类题目没有修改操作，但是要求询问的东西较难维护。其通常为预处理ans[i,j]表示第i块到第j块的答案，然后再预处理sum[i,j]表示前j块i元素的出现次数，然后对于一个询问，只对多余部分进行扫描，然后可以用一些数据结构维护。
又或者预处理第i块到第n块的答案诸如此类。都是没有修改，利用分块的题目。
例题：bzoj4241历史研究，bzoj3289Mato的文件管理，bzoj2821作诗，bzoj2724蒲公英，bzoj3744Gty的妹子序列，都属于这种类型。

但是其实运用数据结构维护信息，上面的所谓“无修改利用分块题目”也可以变成兹瓷修改操作。
例题：bzoj3787Gty的文艺妹子序列。

当然大家熟知的一种，就是离线进行处理的莫队算法，其思路在于对于l~r的答案如果我们可以通过维护而得到l~r+1或是l+1~r（也就是添加和删除），那么可以通过改变做询问的顺序来降低复杂度，将询问左端点所属块为第一关键字，右端点为第二关键字，排序，然后直接做。复杂度非常好证。
例题：jzoj3568小纪的作业题。bzoj3585mex。bzoj3809Gty的二逼妹子序列。

而树上问题可以用树上莫队解决，把序列上莫队弄到树上有各种方法，比如dfs序、括号序等，任君使用。
例题：jzoj3360苹果树。

当然，树上莫队是离线做法，有时候我们需要树上分块。做法是对于每个点，看看其父亲结点所在块是否已经满了，未满就加入其父亲所在块，否则自成一块。
例题：bzoj3720Gty的妹子树。bzoj3729Gty的游戏。

数论相关

数论中有时候会出现一些神奇的类下取整求和的东西，然后研究出其的取值数量很少，从而把相同取值分为一块进行计算。
大家所熟悉的莫比乌斯反演算法就是使用了分块。
例题：jzoj4161于神之怒，jzoj3610wyx，jzoj3117模积和，jzoj3671&bzoj3567江南乐，jzoj1938&bzoj2693Crash的数字表格，bzoj2194jzptab。

其他

有一种间隔询问问题（形如对于区间里所有可以表示为a+ib或模a余b的数进行信息询问），下面以模a余b为例子。这种通常我们会把所有询问分两类，一类能被询问到的点比较少，暴力解决该询问。另一类a和b的取值较少，可以枚举ab然后进行维护。具体的说，如果a大于根号n，我们直接暴力，否则枚举a与b然后用数据结构进行维护。这样算法最终是带根号算法。
例题：2015年蓝桥杯A组的灾后重建。

准确来说，这里应用的根号思想是——存在两个因素乘积一定，一个大另一个就小，然后对两种情况分别击破。

最后

欢迎读者进行补充。