P4198 楼房重建 题解

· · 个人记录

题意可以转化为一个数列 {a_n}，m 次单点修改，每次全局查询一个 {a_n} 的子序列长度（构造方式为从序列左到右选数，后面选的大于前面选的，能选就选。第一项为 a_1 ）。n，m 同阶 在双log下通过。

由于询问区间固定，且单点修改，考虑线段树维护。设一段区间的答案独立，单点修改update时，如果目前在一个节点 rt，我们已经处理了子区间的答案，那么这段区间的答案一定是由左区间答案+以左区间值max为首项之后在右区间乱选的长度（不加首项），考虑解决右部分（使用函数work()），假设目前处理到 now 节点，那么如果左区间max 小于等于首项，那么没用，直接递归右儿子。否则注意到首项不会影响右区间在 now 管辖的区间下的答案 (ans(now)-ans(now<<1)），直接递归左区间计算后返回右加左答案就可以了。

关于时间复杂度分析，在 update 时至多遍历 log 个节点，在每个节点又会 work 一次，每次 work O(log)， 因此单点修改 O( log^2 n ),于是就可以通过了。