楼房重建线段树
题目传送门
显然这道题的题意可以转化为，求从头开始，当前斜率如果大于前面的所有值，则必选，否则不选。
那么，我们考虑，搞一个线段树，每个节点维护两个值，当前区间的最大值，和合法序列长度。
因为是单点修改，所以向下修改的时候是显然的，直接往下递归，但是需要考虑修改过后如何传上去，对于左区间，显然直接继承就好，因为并不会在其前面放上什么东西影响其结果，至于右区间，则需要找到其第一个大于左区间斜率最大值的位置，将其后面的答案加上。
我们考虑对于右区间再次进行递归，每次考虑其左右儿子。
设左区间的最大值为 \(x\)，若当前左儿子的最大值大于 \(x\)，则显然对于当前左右儿子合并时右区间的贡献是可以直接加上的，然后继续递归左儿子。
否则，我们递归右儿子找到答案即可。