线段树复习

1.楼房重建

经典题。先转化题意，将斜率转化为每个点的权值，发现答案是单调递增的。那么就是求单点修改的最长上升子序列。

用线段树维护两个信息当前区间的最大值 mx，当前区间最长上升子序列长度 len。

修改时单点修改即可，考虑如何合并两个区间的 len。可以在线段树上二分。get(o, k) 维护当前区间以大于 k 开头的最长上升子序列长度。

.如果当前区间的最大值小于等于k, 那么len = 0;
·如果左区间的最大值小于等于 k，直接搜索右区间；
·否则答案为 \(get(left, k) + len_o - len_{left}\) 。