楼房重建线段树

link

维护单调序列、点修的线段树。

首先考虑一个楼房被看见的必要条件是前面没有斜率大于它的楼房，不等式可以推出来。

然后本质上是维护一个从 \(1\) 号开始斜率单调上升的序列长度，注意，不能跳跃选择，即某栋楼房能加入序列则必须加入。

线段树维护区间最大值和区间上升序列长度，由于是点修，所以不需要 push_down，来考虑 push_up。

对于一段区间，设其左儿子为 ls，右儿子为 rs。显而易见的一点就是 ls 一定可以加入答案中，考虑右儿子。

设左儿子最大值为 lx，若右儿子中只有一个点，此时容易判断能否加入。

否则，将右儿子分裂成 \(s1,s2\)。

• 若 s1.mx>lx，显然 s2 对 rs 的贡献一定能被加入到答案中，递归去找 s1。

• 否则，s1 必不会产生贡献，递归找 s2。

这样一直只会找一边，时间复杂度 \(O(n\log^2 n)\)。

若不是点修，是区间修改，应该可以用分块思想做到 \(O(n\log^2 n)\)，或许会更劣一点。

剩下不会。

代码不会写。

为什么这么废物呢？