分治相关
感觉整体二分和这几个东西写法差不多，所以钦定他是值域分治。
线段树分治
一般是按时间分治，建立类似线段树的结构，将操作/询问挂到时间节点上，从而避免了难做的删除操作，我只需要撤销到进入节点前的状态即可，通常认为撤销比删除好做，复杂度多个 \(\log\)。
还有的情况是我们需要带着操作或询问区间往下走，这就右端点类似整体二分和猫树了，我们只需要到特定节点计算其贡献再合并即可。
P5787 【模板】线段树分治 / 二分图
给定一张图，有一些边会在给定时间段内出现，对每个时间点判断图是否是二分图。
判断图是否存在奇环，用扩展域并查集，并查集无法支持删除，于是我们考虑线段树分治，用撤销代替删除，用一个栈维护删除信息即可。
P4585 [FJOI2015] 火星商店问题
给定 \(n\) 个集合，每次可以往一个集合内加点，或者查询一个区间集合再最近 \(d\) 次插入操作插入的点 \(\operatorname{xor} x\) 的最大值。
不考虑时间，区间集合 \(\operatorname{xor}\) 最大值用可持久化 trie 就能做到单 \(\log\)。
然后加上时间，查询一个时间区间我们采用线段树分治，虽然感觉这里叫时间分治更好，我们将询问挂到线段树节点上，然后带着所有修改在线段树上往下走，在每个节点用当前所有操作更新该节点询问最大值，然后将所有修改划分为左右继续向走，复杂度 \(O(n\log^2 n)\)。
CF1140F Extending Set of Points
原题面很清晰。
发现只存在两个点对 \((x_1,y_2),(x_2,y_1)\) 时两个点对是相对独立的，所以启发我们将原图看做二分图，那么整张图就是若干完全二分图，边数等于每个联通块的左部点乘右部点数，加边删边用线段树维护即可。
P4319 变化的道路
加边删边求最小生成树。
加边求最小生成树可以直接 LCT，需要删边的话套个线段树分治即可。
猫树分治
猫树分治，又称二区间合并，一种可以用 \(O(n\log n)\) 时空复杂度预处理，\(O(1)\) 处理区间询问的算法，与 cdq 和整体二分类似。
我们考虑线段树上，我们通过 pushup 操作不断合并两个区间，做到查询 \(O(\log n)\) 个区间回答询问，但是如果没有修改操作，我们可以只询问 \(O(1)\) 个区间来回答询问。
即，我们需要找到一个区间，使得其包含我们整个询问区间，且中点落在询问区间内。考虑堆式建树，\(i\) 的左儿子是 \(2i\)，右儿子是 \(2i+1\)，那么显然我们要找到的是 \([l,l]\) 和 \([r,r]\) 在树上的 \(\text{LCA}\)，而如何求出 \(\text{LCA}\) 呢。
因为采用了堆式建树，记 \([l,l]\) 编号为 \(x\)，\([r,r]\) 编号为 \(y\)，那么其 \(LCA\) 编号为 x >> log[x^y]，此处 log 数组的定义在 \(1\) 处为 \(1\)。
其实，在可以离线的问题中我们完全可以类似整体二分，将询问不断分组来找中点也可以。
之后，我们找到了这个大区间，那么我们其实只要预处理出从区间中点出发向左向右的前后缀答案，再做拼接即可，这也要求问题需要有可加性，比如区间最大子段和，\(\{\max,+\}\) 卷积之类的。
P6240 好吃的题目
给定价值和代价序列，\(q\) 次询问，给定
l r t,查询区间 01 背包上限为 \(t\) 的答案。
\(1 \le n \le 4\times 10^4\),\(1 \le q \le 2\times 10^5,1 \le h_i,t \le 200,1\le w_i \le 10^7\)。
发现 01 背包形如 \(\max \{ f_i + f_{t-i}\}\)，即 \(\{\max,+\}\) 卷积，满足区间可加性，直接猫树分治，每次对 \((mid,r]\) 处理前缀背包答案，\([l,mid]\) 处理后缀背包答案，查询时 \(O(t)\) 将两侧背包答案拼接即可。
总复杂度 \(O(nt\log n + qt)\)，跑到了最优解第一页。
P6109 [Ynoi2009] rprmq1
\(\text{4-side}\) 矩形 \(\max\)，询问前给定 \(m\) 次矩形加法。
\(1 \le n,m \le 5\times 10^4,1 \le q \le 5\times 10^5\)。
吓哭了，难点在于想到猫树分治。
考虑 \(\text{3-side}\) 怎么做，我们默认所有矩形都有一边靠在 \(y\) 轴上，那么我们只需要扫描线，然后询问就是急死急询问历史 \(\max\)，复杂度 \(O(q\log n)\)。
然后来考虑 \(\text{4-side}\)，因为历史 \(\max\) 有不可差分性，而根号又做不了，所以我们不能将急死急换掉，考虑将差分换成合并，然后就自然想到 \(O(1)\) 处理合并信息的猫树。
那么，我们只需要将询问挂到对应猫树点上，矩形加法差分后挂到对应点上，猫树上直接前后缀扫一遍就好了，复杂度 \(O(n\log^2 n)\)。
真难写啊哥们，参考了题解区比较好写的做法，写一点细节：
-
对于历史和线段树撤销，我们既需要反着扫一遍减去原贡献，在加数时也要注意先加负的再加正的，删数同理，然后要记得打上清空标记的 tag。
-
在猫树上，为了保证我们每一次扫到全部矩形，我们考虑记录指针表示当前扫到哪里了，然后反复走回中点再加删点即可，这样就很好写了，而且指针只有 \(O(n)\) 次移动。
-
关于猫树，可以提前建出来，然后 \(O(1)\) 找到其覆盖节点。
整体二分
一种基于离线处理某些序列可带修问题的算法，比方说区间动态第 \(k\) 大，实测下来常数是树套树的十分之一。
展开来说，我们的每一个询问都是一个可以二分的问题，暴力做法一般是 \(O(qn\log n)\)，整体二分可以做到 \(O(q\log V \log n)\) 的优秀复杂度。
其主要思想就是，把所有询问和修改放入一个序列中，然后对序列和答案区间同时分治，比方说我们记当前处理的序列区间为 \([ql,qr]\)，答案区间为 \([l,r]\)，当 \(l=r\) 时，显然 \([ql,qr]\) 中所有询问的答案均为 \(l\)，否则当 \(l \neq r\) 时将 \([ql,qr]\) 继续分类下去分治。
P2617 Dynamic Rankings
可离线区间动态第 \(k\) 大。
\(1 \leq n,q \leq 10^5,V \leq 10^9\)。
我们可以把赋初值看做一次插入，一次修改看做一次删除和插入，将其与询问插入序列中，然后分治，每一次用树状数组将答案在 \([l,mid]\) 和 \([mid+1,r]\) 的序列分隔开，大概与 cdq 的思想差不多，之后再继续递归，知道找到答案，代码很好写，跑的很快。
\(\text{cdq}\) 分治
简单写一下够个数。就叫序列分治吧，区别于猫树的是他不需要预处理，而且信息不好合并。
一般用于处理偏序问题，做法大概是在类似线段树的结构上，对于一个区间将其划分两部分，计算左部向右部的贡献，统计总贡献就是答案。
P3810 【模板】三维偏序 / 陌上花开
三维偏序计数
cdq + BIT。
浙公网安备 33010602011771号