序列分治（cdq，整体二分，线段树分治）

· · 个人记录

两区间合并（猫树分治）

见猫树学习笔记。

适用范围：无修改，区间查询可快速合并的信息。

优点是 O(1) 查询。

cdq 分治

适用范围：解决多维偏序问题，即对于每一维，i 处的信息只受到 1 到 i-1 处的信息影响。

做法：分治过程中求出左区间对右区间的贡献。

优点是可以嵌套，空间复杂度线性。

可以在很多允许离线的问题中代替树套树。

例题：1.P3810 【模板】三维偏序（陌上花开） 提交记录

首先去重，按 a 属性为第一关键字，b,c 属性为第二三关键字从小到大排序（后两维顺序没有影响，只需要保证在整个分治过程中，若 (i,j) 满足 i 的每一维分别小于等于 j 的每一维，则 i 在 j 前面）。

然后按 b 属性归并排序。设当前分治区间左端点为 l 右端点为 r 中点为 m。则 [l,m] 和 (m,r] 分别已经按 b 排好序，并且 [l,m] 中的 a 属性都小于等于 (m,r] 中的 a 属性。

对 [l,m] 和 (m,r] 归并的过程中算出 [l,m] 对 (m,r] 的贡献，具体做法是设当前归并时新加入一个数 i（满足 b_i 大于等于之前所有 b_j），若 i\in[l,m] 则在树状数组上对 c_i 单点加，否则查询 c_i 的前缀和加入 f_i。

每次归并结束后需要清空树状数组，可以用打标记的方式实现。

时间复杂度 O(n\log^2 n)。

2.P4027 [NOI2007] 货币兑换

见斜率优化学习笔记例题 4。

3.P4721 【模板】分治 FFT

考虑 cdq 分治时 [l,m] 对 (m,r] 的贡献，容易发现是个卷积，用 FFT 计算即可。

复杂度 T(n)=2T(n/2)+O(n\log n)=O(n\log^2 n)。

注意此题转移是有顺序的，必须先递归左边，再求出左边对右边的贡献，最后递归右边。

有 O(n\log^2 n/\log\log n) 的做法。

4.P4849 寻找宝藏 提交记录

题意是求四维空间的最长不降子序列及方案数（一般的最长不降子序列是两维）。

考虑 dp，i 能向 j 转移当且仅当 i 的每一维都小于等于 j 的对应维。

于是问题转化为四维偏序，可以用 cdq 分治优化。

因为此题 dp 转移有顺序，必须按中序遍历，不方便归并排序。

如果用 cdq + cdq + 树状数组，可以直接 sort，不影响复杂度。

如果用三次 cdq，必须先进行一遍归并排序预处理每层排序结果（见 command-block 的题解），如果用 sort 会多一个 \log。

考虑 cdq + cdq + 树状数组的做法。

首先去重，然后以 a 为第一关键字，以 b,c,d 为第二三四关键字从小到大排序。

然后第一层 cdq 对左区间的元素打一个 0 标记，右区间 1 标记，这样之后只可能 0 向 1 转移。然后按 b 排序，注意要保证若 (i,j) 满足 i 的每一维分别小于等于 j 的每一维，则 i 在 j 前面，所以要用稳定的排序 stable_sort，否则会被 hack。

第二层 cdq 先按 c 排序（同样需要 stable_sort），然后将 d 插入树状数组，维护前缀 \max 即可。

时间复杂度 O(n\log^3 n)。

习题：

P2487 [SDOI2011]拦截导弹

P5445 [APIO2019]路灯 题解

CF848C Goodbye Souvenir

P4690 [Ynoi2016] 镜中的昆虫

线段树分治

适用范围：容易维护插入操作，以及撤销上一个未被撤销的插入操作，但不容易维护删除操作。允许离线。

时间复杂度：一次操作转化为 \log q 次插入操作，复杂度即为插入操作的复杂度乘 \log q。

做法：

记录每次操作的时刻 l 和被删除的时刻 r+1，则此操作仅在时间 [l,r] 内有效。将 [l,r] 转化为线段树上的 \log q 个区间，将这次操作拆成这 \log q 个插入操作。

回答询问时对整棵线段树先序遍历一遍，每访问到一个结点就插入这个结点的所有操作，离开这个结点时撤销这些操作。递归到叶子结点时回答对应时刻的询问即可。

模板题：loj #121. 「离线可过」动态图连通性 提交记录

离线然后线段树分治，就只需要维护加边和撤销加边，查询连通性。

考虑用并查集维护，撤销只需要用一个栈记录 fa 数组的每次修改。

但是路径压缩的并查集单次操作复杂度最坏 O(n)，不停的反复插入撤销同一个位置就有可能卡到 O(nq)。

考虑用按秩合并的并查集，单次最坏 O(\log n)，撤销时多记录 size 数组的修改即可。

时间复杂度 O(q\log n\log q)。

线段树分治还可以代替线段树套线段树，使空间复杂度减少一个 \log。

例题：P3688 [ZJOI2017] 树状数组

此题需要支持矩形修改单点查询，且修改操作具有交换律，可以用树套树 + 标记永久化解决（线段树套线段树的结构不方便下传标记，而标记永久化的适用前提是具有交换律）。

但是树套树比较卡空间，考虑离线分治，按矩形的 x 一维分治。

设当前分治到 [l,r]，上一层分治到 [l0,r0]，只考虑包含 [l,r] 且不包含 [l0,r0] 的修改，以及位于 [l,r] 内的询问，将这些修改和询问按时间 t 排序，然后从前到后处理，对 y 一维建线段树维护即可。

然后求出 [l,r] 中点 mid，对 [l,mid],[mid+1,r] 分别分治即可。

习题：

P5787 二分图 /【模板】线段树分治

P4585 [FJOI2015]火星商店问题

CF1140F Extending Set of Points

CF576E Painting Edges

整体二分

适用范围：答案具有可二分性，但二分判定复杂度过高，可以通过对多个询问同时判定降低复杂度。允许离线。

模板题：P1527 [国家集训队]矩阵乘法

对所有数离散化，考虑二分答案 ans，相当于判断不超过 ans 的数是否有 k 个，就是二维数点，排序 + 树状数组维护，单次判断 O(n^2\log n)，再乘上二分的 \log n，总复杂度 O(qn^2\log^2 n)。

考虑优化，对所有询问同时二分。设当前二分区间为 [l,r]，将 [l,m] 的点加入，还是二维数点。若小于 k 个，则向 [m+1,r] 递归，并且 k 减去 [l,m] 的个数。否则向 [l,m] 递归。

共 \log n 层递归，总复杂度 O((q+n^2)\log^2 n)。

模板题 2：P4175 [CTSC2008]网络管理

同样是整体二分。对修改和询问同时二分，保持修改和询问的相对顺序不变即可。判定可以用 lct/树链剖分等维护。

习题：

P3527 [POI2011]MET-Meteors

CF603E Pastoral Oddities

P5163 WD与地图