专栏文章

题解:P7497 四方喝彩

P7497题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip7qpgo
此快照首次捕获于
2025/12/03 07:32
3 个月前
此快照最后确认于
2025/12/03 07:32
3 个月前
查看原文
有启发性的典板。
考虑一个节点的信息状态:
最后被更新的版本(时间)为 hh,上面的节点的版本不小于 hh,下面的版本不超过 hh
则一个节点被封锁即它在一段版本内失效。
考虑在插入的时候插入版本标记,修改的时候忽略它。
发现这样无法直接处理关系。
额外维护一个结束版本最小值 mnmn,每个时间开始时暴力扫描去掉这些版本标记,处理的时候遇到有标记点跳过即可。
本质上是强制更新某节点的版本至当前时间。
复杂度 O(qlogn)\mathcal{O}(q\log n)

评论

1 条评论,欢迎与作者交流。

正在加载评论...