关于时间标记
查看原帖
关于时间标记
302383
Feyn楼主2023/3/24 17:08

以第一篇题解为例,他说是每个节点维护一个时间标记,含义是当前最小值的贡献次数;然后每次都直接在根节点上打标记,下放的时候是视左右孩子的最小值与自己是否相同来决定是否下放的。

那么蒟蒻想问一下,这道题里这样做一定是对的,因为根节点的最小值一定保持为 00,那么剩下的节点只需要保持和它一样就可以更新答案;假如根节点的答案可能不合法,那么这样计算出来的答案是否就会包含那些是节点中最小值却不一定是 00 的贡献、从而导致错误呢?或者说我上面的那些理解是有误的?

2023/3/24 17:08
加载中...