1 点分治
1.1 思想
思想：选择一个中心，并将跨过中心的所有信息计算。问题会被递归成没跨过中心的信息量，复杂度一般是 \(T(n)=2T(\dfrac{n}{2})+O(F(n))\)。
序列上的点分治也叫做猫树分治。
其特征为：当前所求的信息可以被拆解成两个。
1.2 Travel around China
考虑分治，选择一列并分割，则两边的点想要互相到达一定要经过这一列点。处理跨过这一列的查询。
每层只有 \(d_{i,0},d_{i,1},d_{i,2}\) 三种信息，表示到达三种中心的最短距离。
钦定某种信息最大，剩下两个信息是二维偏序，每层时间复杂度 \(O(n\log n)\)。则总时间复杂度 \(O(n\log^2 n)\)。
1.3 Quick Tortoise
每次选择一行或者一列作为分治中心，处理跨过分治中心的查询。使用 bitset 优化转移，判定时取交。
复杂度 \(O(\dfrac{n^3\log n}{\omega}+n^2\log n)\)。
1.4 rprmq1
考虑按照纵坐标分治，处理跨过 \(mid\) 的所有查询。
在线段树上，区间加，查询历史最值即可。
1.5 永恒
非常好的题。
树上问题，首先处理跨过 \(u\) 的所有查询。对于一个点对 \((x,y)\)，其贡献到 \(x\) 的子树内的查询和 \(y\) 子树内的查询。其权值为 \(lca\) 的深度。
处理 \(lca\) 深度考虑构建一个到根的修改，查询到根的和。对此问题，由于离线，可以构建虚树，从下往上和从上往下做前缀和即可。
1.6 成都七中
点分治，若一个点可以到分治中心，则令 \(x\) 为分治中心即可。递归下去时把已经挂到分治中心上的询问删去。
接下来只需要做一个二维偏序。修改 \(O(n\log n)\) 次，查询 \(O(q)\) 次。如果愿意的话也可以平衡。
2 整体二分
2.1 思想
思想：对于要对 \(q\) 个询问分别二分的问题，考虑维护一个集合 \(S_{[l,r]}\) 表示答案在 \([l,r]\) 中的集合，这样一共有 \(O(n)\) 个区间，每个区间到下一个区间的信息以复杂度 \(O(r-l)\) 变化，总变化量 \(O(n\log n)\)。
其特征为：不同二分问题所需的贡献有大量重叠。
2.2 I 君的探险
需要更多的限制：保证没有孤立点。
考虑树的部分分。我们要确定每个点的父亲。
整体二分，点亮左半边的点，可以判定右边所有点的父亲是否在左半边内。如果不在，则递归到右边，否则是左边。
考虑一般情况，此时若随机打乱点，并跑上面的算法，每次期望删除 \(\dfrac{m}{3}\) 条边，然后再判断是否这些点已经删完即可。
2.3 Best Subsequence
先二分一个 \(w\)，将序列中的元素分成 \(\le \dfrac{w}{2}\) 和 \(>\dfrac{w}{2}\)。
则任意两个小元素之间不会爆限制，两个小元素之间可能可以选一个大元素，但不能选两个大元素。
性质：每个小元素都会被选。证明考虑调整法，如果选了大元素并且还有小元素没选则可以换，否则直接就可以选。于是查询最小值可以计算任意两个小元素之间的答案。
整体二分，此时小元素和大元素之间有转变，可以用数据结构带 log 维护。总共复杂度 2log。
3 线段树分治
3.1 思想
大概有两种，第一是在时间戳上分治，每次一个点的贡献范围是区间。如果可以撤销，那么使用线段树分治可以让消息不用支持删除。
可能还有一种是查询区间补的信息。
3.2 最短路径
模板题，定义 \(s_{[l,r]}\) 表示 \([l,r]\) 的补的两两最短路信息。不需要撤销，只需要暴力计算 \(s_{[l,mid]},s_{[mid+1,r]}\) 即可。复杂度 \(O(n^3\log n)\)。