目录
-
分块思想
-
分块基础操作
2.1 \(O(\sqrt n)-O(\sqrt n)\) 区间加、区间查询
2.2 \(O(1)-O(\sqrt n)\) 区间加、单点查询
2.3 \(O(\sqrt n)-O(1)\) 单点加、区间查询
-
各种分块思路
3.1 对序列分块
-
普通区间和
-
维护区间 \(k\) 大等
3.2 对值域分块
3.3 对操作分块
3.4 对树分块
-
-
莫队
-
定期重构
正文
0.约定
一般地，设块长为 \(B\)，块数为 \(cnt\)。
1. 分块思想
考虑将一个长度为 \(n\) 的序列分成 \(cnt\) 份，那么每份的长度为 \(B=\frac n {cnt}\)。当 \(cnt=\sqrt n\) 时，\(cnt=\frac n {cnt}=B\)。这导致一个很有趣的性质，就是如果对每一份打 tag，最多不会打 \(O(\sqrt n)\) 次；而对每个块暴力修改，每个块最多修改 \(O(\sqrt n)\) 次。分块算法基于这个思想的基础而诞生。具体地说，对一段区间的修改或询问，对中间的整块直接打 tag，对两侧的零散块暴力修改，就可以保证单次操作复杂度为 \(O(\sqrt n)\)。
容易发现，分块本身维护的信息不需要有 可合并性，这是它优于线段树的地方。但是根号带来的复杂度仍然是瓶颈。2e5凭什么卡根号
2. 分块基础操作
2.1 \(O(\sqrt n)-O(\sqrt n)\) 区间加、区间查询
直接做即可。
2.2 \(O(1)-O(\sqrt n)\) 区间加、单点查询
考虑维护差分数组，单点查询就变成了前缀和。
2.3 \(O(\sqrt n)-O(1)\) 单点加、区间查询
考虑维护块内前缀和、整块的前缀和，每次中间的整块直接算而零散用块内前缀和算，修改把前缀和全改了就行。
3. 各种分块思路
3.1.1对序列分块-普通区间和
直接做。
3.1.2 维护区间 \(k\) 大等
对于ABC339G，对 \(cnt\) 块内各自排序并做前缀和，每次询问零散块直接查，整块在排序的数组内二分 \(\le k\) 的位置，直接算前缀和贡献即可。
计算复杂度，单次询问为 \(O(B+cnt\times \log B)\)，B取 \(\sqrt {n \log n}\) 时最优。
对于 P5356 同理，修改时暴力对块重构即可。
3.2 对值域分块
你发现值域分块其实就是序列分块拍到值域上，没啥区别。
3.3 对操作分块
考虑如果一些修改的影响可以直接计算，不妨对询问分块。
例题：CF925E、CF1588F、[APIO2019] 桥梁、 [HNOI2016] 最小公倍数、GDKOI2024 新本格魔法少女
3.4 对树拍平分块
考虑直接把树用 dfs 序拍平，然后可以方便地在上面维护子树信息。但仅限于子树，不如树剖，静态问题也一般用 dsu on tree 代替。至于树分块，应用较少，我也不会。
4. 莫队
概述
莫队算法是一种离线算法，普通莫队可以 \(O(n\sqrt{n})\) 解决一些区间查询问题。这个问题需要满足区间 \([l,r]\) 的答案能快速求出区间 \([l-1,r],[l+1,r],[l,r+1],[l,r-1]\) 的答案。经过一些扩展可以完成修改、上树等操作。
普通莫队
首先考虑一种暴力：维护两个指针 \(l,r\)，暴力地在询问之间转移。比如这一题离散化后维护一个数组表示数字出现的个数，移动指针添数删数即可。
但是这样可能导致指针移动过多，因此还是 \(O(n^2)\) 的。实际上这种暴力与莫队算法只差一个将询问排序：
将序列分块，按左端点所在的块排序，左端点相同则按右端点排序。这样能保证 \(O(n\sqrt{n})\)。
struct query{
int l,r,id;
}q[500005];
bool cmp(query a,query b){
return bel[a.l]==bel[b.l]?a.r<b.r:a.l<b.l;
}
感性地证明一下：对于左端点相同的询问，右端点移动是 \(O(n)\) 的。而左端点有 \(\sqrt{n}\) 个块，相乘就是 \(O(n\sqrt{n})\)。
另一道题：高橋君
这题看似与区间不相关，实际上也可以用莫队。
莫队的本质是维护多个指针，不一定与区间相关，甚至 A+B problem 多组询问也可以用莫队。
对于这题维护指针 \(n,m\)，分类讨论讨论如何转移。
对于 \(m\)：
\[f(n,m+1)=f(n,m)+C_n^{m+1} \]对于 \(n\)：
\[\begin{aligned}f(n+1,m)&=\sum_{i=0}^{m}C_{n+1}^i \\&=\sum_{i=0}^{m}C_n^i+C_n^{i-1}\\&=2\sum_{i=0}^{m}C_{n}^i-C_n^m\\&=2f(n,m)-C_n^m\end{aligned} \]预处理一下组合数即可 \(O(1)\) 转移。
注意事项
- 指针移动的顺序
为了防止出现指针右端点小于左端点的情况，不能随意调换四个循环。设第一步操作左端点，只有三种正确：l--,r--,r++,l++、l--,r++,l++,r--、l--,r++,r--,l++。
- 奇偶化排序
当左端点相同时，如果左端点的块为奇数，右端点从小到大排序，否则从大到小排序。这样的话偶数块的询问可以在奇数块询问解决后，\(r\) 指针返回的途中解决。
bool cmp(query a,query b){
return a.l/bn==b.l/bn?(a.l/bn&1?a.r/bn<b.r/bn:a.r/bn>b.r/bn):a.l/bn<b.l/bn;
}
带修莫队
莫队不只有区间查询，也可支持修改。
多加一维指针 \(x\) 表示查询之前有多少修改，发现一个修改操作的删除撤销也可以 \(O(1)\)，像指针 \(l,r\) 一样移动。
排序方法参照原版莫队三个关键字排序。
带修莫队属于三维莫队，理论上块长取 \(n^\frac 2 3\) 最优，复杂度为 \(O(n^\frac 5 3)\)。一般地，如果莫队有 \(d\) 维，块长取 \(n^{\frac{d-1}{d}}\) 最优，复杂度 \(O(n^\frac{2d-1}{d})\)。
括号序树上莫队
用 dfs 序。
莫队的在线化改造
5. 定期重构
用线段树1为例，每 \(\sqrt n\) 次操作重构整个序列，每次询问考虑上次重构到这次操作对这段的影响。
例题：数列分块入门6
用 vector 存储，考虑当一个块大小超过 \(2\sqrt n\) 时，对其分成两个块。分析一下复杂度是正确的。
标签：cnt,分块,sqrt,学习,笔记,端点,区间,莫队 From： https://www.cnblogs.com/lgh-blog/p/18042701