我怎么什么都不会了，快速过一下这几个。
单侧递归
常用于处理依赖于前缀不可差分信息的维护，比如含有前缀 \(\max\) 之类的信息，复杂度会多一个 \(\log\)。
本质是在 pushup 的时候向某一侧子树递归求解，然后剪枝保证复杂度。
P4198 楼房重建
给定平面内若干线段，前缀最高的线段可以被看到，\(m\) 次修改，每次修改后查询有多少线段可以被看见。
模板题。
其实就是动态前缀 \(\max\) 计数，考虑线段树上每个节点维护当前区间最高点和区间 \(\max\) 个数。
pushup 时，显然合并到大区间对左区间没有影响，考虑左区间对右区间的影响，具体来说，我们向右侧递归查询有多少 \(\max\) 会被左侧更新掉。
记左区间最大值为 \(k\)，如果当前区间第一个 \(\max\) 都大于 \(k\)，则对当前区间没有影响，返回当前区间答案，反之，若果当前区间最大值都小于 \(k\)，那么当前区间没有答案。
然后考虑向左右递归的情况，显然我们只需要找到第一个大于等于 \(k\) 的位置，如果在右侧，那么直接递归即可，如果在左侧，那么我们要加上右侧的贡献，而右侧的贡献是什么呢，我们不能直接取右区间的答案，因为也需要考虑当前左区间的影响，也就是需要继续以左边最高点当作 \(k\) 向右递归。但是我们此时发现，这个情况我们已经算过了，就是当前大区间的答案，而当前左区间的贡献原本是直接加上来的，再减掉就好了，所以大区间答案减掉左区间答案就是右区间答案！
由此，我们就保证了每次只会向一侧子树递归，复杂度和线段树二分等价，每次 pushup 复杂度 \(O(\log n)\)，总复杂度 \(O(n\log^2 n)\)。
\(\text{Submission}\)