preface

感觉三种分治算法容易搞混并不容易区分它们使用的场景和题目（虽然有些题目根据性质可以使用多种分治），所以还是要归纳一下

线段树分治

Part1

主要是处理一类带有撤回的问题，也就是一次修改只对一段区间生效（这里的区间指的是时间）

即区间修改，单点查询

流程大致是把区间修改挂在线段树对应的节点，然后便利一边线段树，叶子节点就是单点查询

所以线段树分治需要一个支持插入和撤回的数据结构，如可撤回并查集..

[CF813F]Bipartite Checking

题目大意

给你一个由\(n\)个顶点组成的无向图，最初在图中没有边。

同时给你\(q\)次查询，每次查询时会向图中添加一个无向边或者删除一个无向边

在每次查询之后，检查图是否为二分图

solution

全局修改，单点查询

然后用可持久化并查集搞一下

[CF603E]Pastoral Oddities

题目大意

给定一张 \(n\) 个点的无向图，初始没有边。

依次加入 \(m\) 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。

若存在，则还需要最小化边集中的最大边权。

solution

全局修改，单点查询

先是一个小tip：要求图的度都为奇数，等价于要求图的连通块大小都为偶数，证明：

必要性：反证，考虑若有一个连通块大小奇数，那么图的总度数为奇数，不成立，证毕

充分性：若有把一个偶数大小连通块变成树，一个点若有奇数个儿子，就断父亲的边，否则就上传，可以发现上传的子树大小为奇数，独立的子树大小为偶数，所以到根节点的度一定为奇数，证毕

然后可以想到一种LCT做法

首先能加边就优，显然因为奇+偶=奇，偶+偶=偶，奇+奇=偶，所以奇数连通块只会减小

我们用类似维护最小瓶颈生成树的方式维护这棵生成树，如果加入一条小于当前答案的边，那就把它加入树中，并断掉最大边，判断合法性。若合法，则继续断边。可以发现这样贪心是优的，类似dij的流程

但是这里是线段分治总结...

我们发现一条边它在树边集中出现的一定是一段连续区间，因为它只能在加入到删除前出现，但是我们并不能找到它结束的位置，于是我们考虑从后往前做，找到一条边最后的出现时间，然后再插入线段树

Part2

当然还有单点修改，区间查询的题

单点修改，区间询问，要求修改独立贡献答案

然后对于单点修改就是类似标记永久化的思想，把根到叶子的全部节点都挂上该修改，所以就不要求可撤回

P4585 [FJOI2015] 火星商店问题

题目大意

有\(n\)家商店，操作使\(s\)号商店在第\(i\)天进一个价值为\(val\)的货物（当日就可以卖掉），询问是给出一个数\(x\)，在\([l,r]\)天里\([L,R]\)号商店与\(x\operatorname{xor}val\)的最大值是多少。每个商店都会有个永远的货物。

solution

用上面的方法把修改和查询挂好，然后发现查最大值，满足合并性

然后就等于\(n\log n\)去掉了时间维，于是就变成可持久化tire，详情见可持久化trie

Part3 猫树分治

只可以处理不带修的问题...

但是询问不用拆成log个，可以\(O(1)\)

具体流程就是对于线段树每一个节点，在mid处维护一个前缀和后缀，然后对于跨立mid的询问就直接计算，否则下传

[CF1100F]Ivan and Burgers

题目大意

给定\(n\)和\(a_{i\dots n}\)，有\(q\)个询问：给定\(l,r\)，求在\(a_{l\dots r}\)中选取任意个，使得他们的异或和最大。

solution

首先考虑直接线段树维护，但是发现把合并线性基的时间复杂度是\(log^2\)的，配上线段树就是\(log^3\)

所以考虑猫树分治，每次计算答案时只把一个前缀和一个后缀合并

cdq分治

cdq分治是典型的暴力算法，大体流程是分治处理左右区间内部的答案，每次计算跨立左右的答案，

典型例题有三维偏序（原理是用一个log是偏序少一维），还有一些横坐标无序的凸包题（实现凸包合并）

整体二分

整体二分可以处理单次询问要二分\(O(n\log V)\)的带修问题，进行整体二分+一些数据结构维护（一般是BIT），可以做到\(O((n+q)\log V\log n)\)

具体流程是二分值域，然后判断答案和修改在哪个区间，然后放进对应区间，然后向下做

由于放进右区间的询问要减去左区间的影响，所以要求有可减性