非套路分治 ​

分治概述 ​

很多时候，分治可以被带有分治结构的 DS 代替。但是分治是 DS 题最基本的方法，只要是一道题，基本上都可以用。

分治的性质 ​

我们以线段树的结构来分析分治的结构性质，记一个节点的大小为其对应线段长。

• 层数只有 log 层。
• 所有节点的大小总和是 $n\log n$。
• 每个节点的子树大小和为 $n\log^2 n$。
• 每个节点的两个子节点的大小几乎相等。

分治的常见运用 ​

优化背包合并的复杂度 ​

闵可夫斯基和，FFT 都可以用此优化。有时也可以写成倍增形态。

去掉一维偏序 ​

即 CDQ 分治。在某些问题中也可以处理修改操作，例如点的统计问题。

处理一般的多次询问问题 ​

核心：将跨过中线的询问去掉一半，然后将另一半以及其他的询问继续递归。例如：跳端点分治。

例题 ​

ARC184B ​

观察到当序列中的某一种元素已经大于假币数量时，我们就可以确定这个序列那些是假币。所以要让序列尽可能长，联想到分治的平衡结构，尝试分治。考虑正确性，只要序列长度 > $2m$，那么序列就一定能确定，所以至少可以减少 $1000 / 20 = 50$ 次询问。

Gym102331J ​

显然有背包 + 闵可夫斯基和的做法，复杂度 $O(N^2)$。考虑到本题不太有其他做法，所以尝试优化当前做法。瓶颈在闵可夫斯基和，发现复杂度就是每棵子树的大小乘上其合并的次数再求和。联想到分治的层数少，可以尝试用分治合并。但是复杂度还是不对，因为每个子树都被合并了一遍。联想到启发式，分一下轻重儿子，轻儿子分治合并，重儿子在重链上分治合并。

rqrmq1 ​

略

整体二分 ​

适用情况 ​

不强制在线，所有询问都能用二分解决（可以有单点修改）。

此类问题的常见思路 ​

• 每个询问二分：复杂度平方对数。
• 暴力均摊：复杂度平方。
• 整体二分：主体随二分的范围变小而变小，复杂度线性对数。

整体二分的重要性质 ​

同一层保证二分的值单调递增，可以一起处理。

刷题 ​

区间 k 大值 ​

经典题，想怎么做就怎么做。如果带修呢？将修改看作减掉一个点和加上一个点，和询问一起按时间放进操作序列，然后每次按值域分治操作。

多次询问无向图任意两点的 min/max 最短路 ​

kruskal 重构树板子，但整体二分也能做，结合一下可撤销并查集，每次只加入 <= mid 的边。

图分治 ​

专门处理网格图上的抽象问题。例如：

• 多次查询。
• 最优化子矩形。

例题 ​

• ZJOI 旅行者。
• 各种关于子矩形的题目。