线段树进阶
线段树合并
设总节点数 \(T\)，每次 \(O(1)\) 合并两个节点总节点数减少 \(1\)，所以复杂度 \(O(T)\)。
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
P3224 [HNOI2012] 永无乡
线段树分裂
单次分裂一个区间，很无脑地就是 \(O(\log n)\) 的。
P5494 【模板】线段树分裂
势能均摊线段树
吉司机线段树
单侧递归线段树（类楼房重建问题）
P4198 楼房重建
题意为求斜率数列，严格前缀最大值的个数。
我们考虑使用线段树维护。
如何合并答案？每个区间若左子区间最大值大于等于右子区间最大值，则无需考虑右子区间；否则用一个 Calc 函数，计算右子区间大于传入的左子区间最大值的数的答案：
- 左侧最大值大于传入的值，只需 Calc 左侧，加上右子区间的答案。
- 否则只需 Calc 右侧。
复杂度 \(O((n+q)\log^2n)\)。