专栏文章

题解:P14588 [LNCPC 2025] 前线支援

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

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mimzrp4u
此快照首次捕获于
2025/12/01 18:13
3 个月前
此快照最后确认于
2025/12/01 18:13
3 个月前
查看原文
把静态 Top Tree 建出来,每个节点维护加常量加到上界点的距离加到下界点的距离三个标记,子树加和子树补加都可以直接搜,容易发现每次只会走一边。
实现上可以用 Top Tree 上的 DFS 序判点在哪个子树,操作可以讨论 yy 是否在 xx 子树内,在子树内就差分一下。用 O(nlogn)O(1)\mathcal O(n\log n)-\mathcal O(1) 的 LCA 求距离就是单 log\log 了。

评论

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

正在加载评论...