P4198 楼房重建

P4198 楼房重建

求从 \((0,0)\) 往上看能看到多少栋没被挡住的楼房，带修改。

对于带修改的题目，我们需要快速维护，就需要用到数据结构。这时候通过直觉可以想到，问题是可以分为子问题然后合并得到的，所以我们考虑线段树。

观察到能被看到的楼房，从左到右斜率递增，即我们需要维护斜率递增的序列。

考虑子区间需要维护的信息，发现该区间对其他区间的影响只跟其斜率最大值有关，所以一个是维护区间斜率最大值 \(\max\)。然后再维护一个区间答案 \(cnt\)，表示从该区间的左端点能看到的楼房数量。

怎么合并？记 \(u\) 为合并后的区间，\(ls\) 和 \(rs\) 为左右区间。首先显然左区间 \(ls.cnt\) 一定能贡献到 \(u.cnt\) 中；右区间的答案显然不能马上得出，我们在把右区间细化成更小的问题，分类讨论一下。记右区间的左区间为 \(rsl\)，右区间的右区间为 \(rsr\)。

如果 \(rsl.max<ls.max\)，那么 \(rsl\) 所有点都看不到，舍去，然后继续考虑 \(rsr\)。

否则 \(rsr\) 的贡献只和 \(rsl.max\) 有关，可以发现贡献即为 \(rs.cnt-rsl.cnt\)，然后继续考虑 \(rsl\)。

这部分思考变成代码也很简单，由于每次只会递归一个区间，复杂度单次是 \(O(\log n)\)。

所以是 update 的同时套一个 \(O(\log n)\) 的合并区间，总复杂度是 \(O(n\log^2 n)\)。