专栏文章

题解：P14623 [2018 KAIST RUN Fall] Coloring Roads

ccomplexor管理员
P14623题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimyxzct
此快照首次捕获于
2025/12/01 17:50
3 个月前
此快照最后确认于
2025/12/01 17:50
3 个月前
查看原文
题意即为：给定一棵有根树，维护以下两种操作：
  1. 将点 xx 到根路径上所有边颜色改为 cc；
  2. 查询出现 kk 次的颜色种数。
考虑维护同色树上连续段。具体地，当修改 xx 到根的路径时，将 xx 到根上的所有点从它们原来所在的连续段断开，并将这些点缩成一个新的连续段。
不难发现这就是 LCT 的 access 操作，直接 LCT 维护即可做到 O(Qlog⁡n)\mathcal O(Q\log n)。
下面证明一下 LCT 的 access 操作中虚实边切换次数均摊是 O(log⁡n)\mathcal O(\log n) 的，即上面过程中连续段改变次数是均摊 O(log⁡n)\mathcal O(\log n)。
证明
对树进行重链剖分（这是在操作中不会改变的）。定义这棵树的虚实链划分的势能为是虚边的重边数量。 注意到一次 access 中虚实边切换次数不超过操作的点到根的路径上虚边数量的两倍。考虑这些虚边的轻重性：
  1. 如果是重边，那么遇到一条这样的边时就会使势能减一，所以这部分复杂度可以摊到势能中；
  2. 如果是轻边，由重剖性质，每次操作只会遇到 O(log⁡n)\mathcal O(\log n) 条，每条都至多使势能加一（这条轻边变成实边导致一条兄弟重边变成虚边）。
初始时势能即为重边数量 O(log⁡n)\mathcal O(\log n)，势能总增加量 O(Qlog⁡n)\mathcal O(Q\log n)，故第一种情况次数均摊 O(log⁡n)\mathcal O(\log n)，第二种情况次数严格 O(log⁡n)\mathcal O(\log n)。
所以也可以用重链剖分加数据结构维护连续段做到 O(log⁡2n)\mathcal O(\log^2 n)，或者用 Treap 等平衡树实现 LCT 的操作也是这个复杂度。
至于为什么 LCT 是单 log⁡\log 我不会证，我连 splay 都不会证。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...