kb的数列分块&整除分块入门题单

题单适合人群 $$\color{blue}\boxed{tg+}\color{black}/\color{purple}\boxed{sx}$$ **update**： $\boxed{\mathit{1}}$ 2020.8.23 加入【NOI2020】 时代的眼泪 ### Part 1 数列分块 数列分块是一种很~~暴力~~优秀的数据结构，它可以做到许多例如线段树,平衡树等做不了的操作。 先是LOJ分块入门$9$题 [Link](https://loj.ac/problems/search?keyword=%E5%88%86%E5%9D%97%E5%85%A5%E9%97%A8) 然后就是hzwer大佬的题解,个人认为讲的还是比较详细的 [Link](http://hzwer.com/8053.html) 下面就是洛谷中的例题，持续更新中 #### 低档—中档题 P2801 和LOJ分块入门2基本类似，可以当做一个双倍经验，大概就是每块建个vector，每块都放进vector里边，询问时二分，角块修改时暴力重构就OK。 P4145 LOJ分块入门中的题目，大概就和线段树的做法差不多，暴力开根，然后统计有多少块已经都是 $1$，就不用修改了。 P4168 神仙题，LOJ分块入门9,仿照hzwer的方法，直接统计块i~j之间的众数，然后把所有数的出现的下标放进每一块对应的vector里边，询问的时候直接用upper_bound-lower_bound查询角块的出现出现次数，和中间的整块已经预处理了的比较一下，就做完了。其实还有其他的一些比较复杂的预处理方法，可以看题解研究研究。 P5356 lxl卡的分块神仙题，朴素的方法就是直接像P2801一样放进vector里边二分出现次数，然后再在外面套一个二分出现次数的二分，就可以做到 $O(n\sqrt{nlogn}logn)$，但是被lxl卡掉了=.=，所以我们可以用一些膜法来优化，1.将角块修改的地方不用直接排序，可以用归并排序讲一些无序和有序的数列段和起来，就将修改的复杂度优化到了 $O(\sqrt n)$。2.询问的时候，将两边不完整的块归并到成一块，合起来查询，从而降低复杂度。这样搞复杂度就是 $O(n\sqrt nlogn)$ P5309 分块+根号分治。考虑对x的大小分类讨论。 若x⩾ sqrtn则我们暴力给每个位置加，需要加的次数为O(sqrt n)次。由于需要查询区间和，用分块维护，总修改、查询复杂度为O(m\sqrt n)。 若x< sqrt n，我们需要用另外的方法维护。 注意到单次修改是针对整个序列的元素，所以对x,y相同的修改，我们可以累加它的贡献。 我们对每个x，维护y的前缀、后缀和。对于一次询问，我们可以当成把序列分成了若干个大小为x的块。中间的整块元素，每个块里肯定所有的yy都有，增加的贡献就是关于xx的修改总和。所有块的贡献相同，可以 O(1)算。边角的话，由于我们记录了前缀、后缀和，也可以 O(1)算。两个端点在同一个块中，则直接前缀和相减即可。（摘自 mrsrz 的题解） #### 中档—高档题 真正可怕的大分块来了,加油消灭他们（已经自动过滤特别难的题目，大家可以去挑战一下） P5046 对于整个区间，我们预处理出 L[i][j]（以j为左端点，第i块的右端点为右端点），R[i][j]（以j为右端点，第i块的左端点为左端点），P[i][j]（以i块的左端点为左端点，j块的右端点为右端点）的逆序对数的个数，最后直接1+2-3就OK了,对于两边的角块，直接在最开始对每块排好序，询问时用归并排序的方法统计一下就OK了 。 P5048 也是神仙题（怎么lxl那么神仙），首先我们考虑像蒲公英那样，统计区间众数，然后最后想之前那样upperbound-lowerbound一下，复杂度大概是 $O(\sqrt{n}logn)$ 的,但是这样一搞肯定是过不了的（~~能过才有鬼了~~），所以我们换种思路，我们考虑不直接统计众数了，我们直接统计众数出现次数，然后还是那样，把一个数出现的下标放进vector里边。然后就是角块的查询了，这也是这题最经典的一个优化的地方，我们事先统计好到了i这个位置的时候，有多少个和$a_i$相等的数出现过(直接在之前放的vector取个size就OK)，统计左边角块的时候，我们可以考虑这段代码： `while(cnt[i]+ans<(int)s[a[i]].size()&&s[a[i]][cnt[i]+ans]<=r)ans++;` ans就是目前找到的区间众数出现次数。 这样弄是因为，如果cnt[i]+ans<size,就说明了这个数的出现次数至少为ans+1,所以我们就把ans往上抬，直到超过了，我们再往后面去找。右边块也差不多： `while(cnt[i]-ans>=0&&s[a[i]][cnt[i]-ans]>=l)ans++;` 因为数的边界为$2\times\sqrt n$,所以复杂度可以保证在$O(\sqrt n)$ 这两道是Ynoi2019模拟赛中两道分块解决的经典区间点对问题,至于为什么我没有把II拿进来，因为那是lxl的神仙二次离线莫队（。 P3793 分块优化ST表，大概就是把ST表分块，然后统计每一块的前后缀最大值，就可以在$O(1\sim\sqrt{n})$的时间里完成查询并做到节省空间的效果，这种方法的应用空间很广泛，甚至可以拓展到所有有结合律的函数。 估计你做完这些题目之后，分块就会有很大的进步的。 ### Part 2 数论分块 关于整除分块（也叫数论分块）,可以参考我的blog(可能表格有点炸裂，不过也能看看吧) [Link](https://www.luogu.com.cn/blog/comeon123/solution-uva11526) ~~其实整除分块跟分块没什么关系，就是借着分块整块处理的思想，优化复杂度而已。~~ UVA11526 板子题，不多说。 P3935 比较妙的一题，套了两次整除分块，还有比较精巧的推式子，值得一做。 P2261 转换一下也是模板，只是看看你能不能转换过来了。 P2260 应该是整除分块好题了，建议尽量不看题解自己做。 因为洛谷的整除分块的题目比较少，其它用到整除分块的题目基本上都是莫反了，所以就没有加进来，如果有其他的好题欢迎提供。 希望本题单能让大家有所收获~