题解：P7497 四方喝彩

· · 题解

有启发性的典板。

考虑一个节点的信息状态：

最后被更新的版本（时间）为 h，上面的节点的版本不小于 h，下面的版本不超过 h。

则一个节点被封锁即它在一段版本内失效。

考虑在插入的时候插入版本标记，修改的时候忽略它。

发现这样无法直接处理关系。

额外维护一个结束版本最小值 mn，每个时间开始时暴力扫描去掉这些版本标记，处理的时候遇到有标记点跳过即可。

本质上是强制更新某节点的版本至当前时间。

复杂度 \mathcal{O}(q\log n)。