本文会持续更新…….
前言
本篇文章是菜鸡Herself32做过一些分块题之后的总结, 所以写的比较屑/kk.
其实这东西就是Herself32做过的一些分块题的整理, 可以当成一个Problem List看看.
当然如果您觉得这些题太水或者说博主写的很sb, 也请轻喷啊qwq
LOJ6277
最基础的分块题了吧, 对于每一个块记个tag, 整块加法改tag, 零散元素就暴力改.
查询的时候记得把a[i]加上tag再输出.
LOJ6278
用一个vector维护块内的数字, 然后给每一块排个序, 整块查询的时候直接二分lower_bound一下就完了, 零散元素就暴力查.
因为区间加法并不影响整块的有序性, 那么我们只需要对离散元素所在的块重新排序即可.
这样的话查询的时候对于整块就应该以v - tag为关键字查找.
LOJ6279
考虑沿用上一个题的思路, 只需要改一下二分的东西即可.
首先lower_bound找出位置, 然后从vector的begin开始枚举然后取max即可.
LOJ6280
对于每一个块记个sum, 表示这个块的元素之和.
对于零散元素, 直接暴力修改a[i]和sum[Belong[i]], 查询的时候暴力加a[i] + tag[Belong[i]].
对于整块, 修改就直接改tag数组, 查询则直接加上sum[i] + tag[i] * block即可.
LOJ6281
考虑一个$10^9$级别的数, 被开$5$次方之后就变成$1$了.
所以我们开一个CSQRT数组表示某个块里面是否还有$>1$的数字, 如果没有那就不用开了.
那么利用这个性质, 直接暴力操作即可, 其他和之前题目一样.
LOJ6282
在数据随机的情况下, 每个块会被等概率的插入元素, 用一个vector维护一下, 复杂度还是$O(m\sqrt{n})$.
但是如果出现极限情况, 即一直向一个(或较少的几个)块中插入, 就会导致复杂度的变化.
那么考虑设立一个阈值$\alpha$, 如果当某一个块的大小超过了$\alpha \times block$那么就进行重构.
经过一些神奇的分析, 我们可以认为$\alpha = 20$时对于本题来说较优.
当然我们也可以每进行$\sqrt{n}$次插入就进行一次重构, 复杂度也是$O(m\sqrt{n})$的.
LuoguP3396
考虑数据分治, 以$\sqrt{n}$为界限.
设$f_{i,j}$表示在$\mod i$意义下余数为$j$的数的总和, 这显然可以$O(n\sqrt{n})$预处理出来.
小于$\sqrt{n}$的就直接输出f内的对应答案, 大于就暴力算即可.
LuoguP2801
几乎是LOJ6278的重题, 二分的时候用总数减掉lower_bound出来的数即可.
由于是半年前写的题, 所以码风比较屑, 就不放出来丢人了.
LuoguP3203
考虑对于每一个点维护两个值, 一个是从这个点开始需要弹多少次才能被弹出这个块, 一个是被弹出去之后到了哪里.
查询就沿着维护的第二个值蹦蹦跳跳的加一遍完事, 修改就块内暴力重构.
由于是半年前写的题, 所以码风比较屑, 就不放出来丢人了.
LuoguP3645
一个显然的想法是, 把doge们从起点和它所能到达的所有点连边, 然后跑最短路, 但这样显然不行(显然的想法显然不行).
那么如果我们把doge们跳跃过程中的每一个一个点和下一个节点连边, 可以吗?
这个看起来还挺有道理, 但如果我们从中间某个点出发, 这个做法就莫得了.
考虑用分块优化(Upd: 这玩意是根号分治)建分层图, 建立$\sqrt{n}$层图, 对于前$\sqrt{n}$个点, 在子图中每个点$i$连向$i+P_i$和$i-P_i$, 然后这些点就只需要连一条边权为$0$的边向子图中的自己即可.
其他的点就直接按照暴力的连边方法, 然后我们跑一遍最短路就完了.