因为每次跳一个同色段就会少一个颜色段
最后会把经过的段的颜色全合成一种
by hater @ 2022-04-02 15:11:13
@[hrgd](/user/152234) 你首先可以直观感受，发现这个 access 和 LCT 的 access 并在代码上没有本质区别，所以时间复杂度是对的。
感性理解的角度来看，显然相同的颜色在树里是连续的，可以看成该树是由**相同颜色的点构成的 Splay 森林**组成的，每次 $1$ 操作就相当于要把一段根到节点的路径拉成一条链，根据 LCT 的时间复杂度证明肯定是对的。
by FutaRimeWoawaSete @ 2022-04-02 15:23:09
这种颜色段问题大都能势能分析时间复杂度吧。
by LingerFeng @ 2022-04-02 15:28:52
@[FutaRimeWoawaSete](/user/132533) 不太能理解这个颜色段个数跟 access 函数的联系是什么，您能不能详细一点啊
by hrgd @ 2022-04-02 15:43:09
@[hater](/user/100114) 能不能证明一下这个级别啊
by hrgd @ 2022-04-02 15:45:04
@[Zcus](/user/33339) 但是你一个颜色段不一定会一次删完啊
by hrgd @ 2022-04-02 15:52:29
@[Zcus](/user/33339) 这跟颜色段个数有什么关系啊
by hrgd @ 2022-04-02 15:54:16
把每个点的状态看成是否与重儿子同色，一次操作带来的影响是 $\log$ 级别的。
by gyh20 @ 2022-04-02 16:01:25
@[gyh20](/user/41476) 应该是均摊 $\log$ 级别吧，例如毛毛虫形的树就可能一次操作最坏 $\mathcal O(n)$/yiw
by 玄燕本燕 @ 2022-04-02 16:24:52
@[玄燕本燕](/user/89645) 我的“影响”大概指的就是势能（与重儿子不同色的个数），所以是均摊。/kk
语文不好，见谅。
by gyh20 @ 2022-04-02 16:33:50