☆ 启发式 ☆ 合并！ ☆ 分裂！ ☆

我不知道为啥要起这个标题。

启发式合并就是一个思想，把小的往大里合。

感性理解，就是每次合并一定会使集合大小翻倍，于是复杂度仅多一个 \(\log\)。

树上启发式合并

难维护的子树节点信息可以树上启发式合并。

一般会用到 set，map，或者需要手写平衡树进行维护信息。

启发式分裂

有一个区间，每次把它分裂成两半，然后计算两半之间的答案。

直接计算显然是 \(n^2\) 的，但是我们每次可以用较小的一遍去计算较大的一边的贡献。

因为这东西本质上就可以看作是一个树形结构，所以其实和树上启发式合并是一样的。

单调栈/笛卡尔树

对于区间 \(\min / \max\) 的问题，\(R_i-L_i\) 的总和是 \(n^2\) 级别的，但是 \(\min\{i-L_i, R_i-i\}\) 就是 \(n \log n\) 级别的。