分治

401rk8 · 2022-08-16 12:25:55 · 个人记录

cdq 分治

本质上是滚动式的树套树。分治过程是外层树的遍历，任意时刻内层树只需要维护 O(n) 个点的信息，从而优化掉空间上的一个 \log

用于解决偏序问题。要求操作对询问的贡献独立。需要明确什么保证左区间都 < 右区间，区间内什么有序

高维偏序

流程：先递归子区间，然后处理左区间对右区间的贡献

LG3810 【模板】三维偏序（陌上花开）

先按 a 排序，再 cdq 分治。考虑左区间对右区间贡献时限制只剩下了 b,c。把左区间视作修改，右区间视作询问

一种做法是把当前区间按 b 排序，并区分出属于哪个子区间。再嵌套一层 cdq 即可

另一种是把左右区间分别按 b 排序后双指针。扫到一个询问是 b< 它的修改已全部完成，使用 BIT 维护 c 即可

时间复杂度 O(n\log^{2}n)，排序部分可以用归并做到单 \log 但不是瓶颈

LG4390 [BOI2007]Mokia 摩基亚

把时间也看作一维。矩形容斥成两/四个前缀，问题变成了 (\text{时间},x,y) 的三维偏序

loj2880「JOISC 2014 Day3」稻草人

按 x 排序有分治，计算跨过中线的矩形

对于一个右上角 p，合法的左下角一定满足 x 单增，y 单减，且左下角的纵坐标要大于右区间中 p 左下方最大的纵坐标。左右分别按 y 排序，左边维护一个 x 单减的单调栈（只有这些点可能成为左下角），右边维护 x 单增的单调栈（加入当前点之前的栈顶就是右区间中 p 左下方最大的纵坐标），在左边的单调栈上二分即可求出不满足第二个条件的点数

优化转移

流程：先递归左区间（此时左区间的值已经计算完毕了），然后处理左区间对右区间的贡献，然后递归右区间

LG4093 [HEOI2016/TJOI2016]序列

设 mx,mn 为一个位置能变化成的最值，f[i] 为以 i 结尾的答案，能转移到 i 的 j 满足三个条件：j<i,val[j]\le mn[i],mx[j]\le val[i]

然后直接上三维偏序

维护凸包

不在这里展开

整体二分

分治树本质上是权值线段树作外层树的遍历，因此把分治树保存下来即可强制在线

顾名思义，用于同时对多个询问二分。若 check(mid) 时建立 DS 的时间远大于判定一次，那么对于多个需要 check(mid) 的询问就可以只建一遍 DS 从而优化复杂度。要求修改的贡献与判定标准无关

询问的答案可二分且修改对判定标准的贡献相对独立，且贡献的值与判定标准无关。因此如果我们已经计算过某一些修改对询问的贡献，那么这个贡献永远不会改变，我们没有必要当判定标准改变时再次计算这部分修改的贡献，只要记录下当前的总贡献，再进一步二分时，直接加上新的贡献即可。——《浅谈数据结构题的几个非经典解法》

分治