分块莫队与cdq分治搞搞.pdfVIP

分块、莫队与 cdq 分治搞搞 东北师大附中 neither_nor 目录 • 普通分块 • 树上分块 • 莫队 • 莫队的各种变种 • cdq 分治 分块 • 对于序列上的问题，如果我们能高效地处理修改对区间信息的影响，并高效地合并区间 信息，那么我们可以使用线段树解决，而如果我们无法高效地合并区间信息，我们就要 使用分块算法 • 故名思议，把整个序列分成若干块，每块大小为 S • 在修改时，对整块打标记，对两端零散的点暴力修改，询问时整块直接查询块信息，两 端零散的暴力查询 • 一般一次修改 / 询问的复杂度是 O(S+N/S) 或 O(S log N+N/S log N) 的 • 所以一般 S 取根号 N 为最优 • 另外，分块算法还经常应用于强制在线的题目当中 分块 • 简单的应用：长度为 N 的序列，区间加单点查询，查询次数特别多所以要求修改 = 根 号 n ，查询O(1) 分块 • BZOJ3343 教主的魔法 • 教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每 个英雄看。于是 N 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 1 、 2 、……、 N 。 • 每个人的身高一开始都是不超过 1000 的正整数。教主的魔法每次可以把闭区间 [L, R] （1≤L≤R≤N ）内的英雄的身高全部加上一个整数 W 。（虽然 L=R 时并不符合区间的 书写规范，但我们可以认为是单独增加第 L （R ）个英雄的身高） • CYZ 、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 [L, R] 内有 多少英雄身高大于等于 C ，以验证教主的魔法是否真的有效。 • WD 巨懒，于是他把这个回答的任务交给了你。 • N≤1000000 ，操作数 =4000 分块 • 2724: [Violet 6] 蒲公英 • 强制在线询问区间众数 分块 • BZOJ2906 颜色 • 给定一个长度为 N 的颜色序列 C ，对于该序列中的任意一个元素Ci ，都有 1=Ci= 。对于一种颜色 ColorK 来说，区间 [L,R] 内的权值定义为这种颜色在该区 间中出现的次数的平方，即区间 [L,R] 内中满足 Ci=ColorK 的元素个数的平方。接下来 给出 Q 个询问，询问区间 [L,R] 内颜色 [a,b] 的权值总和。 树分块 • 网上有很多的树分块方法，不过多数都听着就不太靠谱，不过还是能 A 题 • 这里就介绍一种靠谱的分块方法，由邹逍遥在 2015 年集训队论文中提出先选定块大小 S ，然后选定所有深度 %S 等于 1 ，并且子树大小 =S 的点作为关键点 • 每个点所属的块就是他往上找第一关键点的块 • 这种方法无法保证块的大小，不过可以保证块内任意两点间距离是 O(S) 的，并且相邻 两块之间的点的距离也是 O(S) 的（两块相邻指关键点之间的路径上没有其它关键点） 树分块 • 具体应用主要在于树上莫队，等会介绍 • 邹逍遥的论文里提到了一些不是莫队的树分块的题目，比较复杂，有兴趣的同学可以去 看看，如果对各种分块感兴趣也可以去看一下他的论文，还有很多其他的东西 莫队 • 莫队并不是什么队列数据结构 ，是一个叫莫涛的人发明的