势能相关难维护的用分块——分块过程维护跨块的:CF1491H / P7446

2023-12-19 23:38:04

https://www.luogu.com.cn/problem/P7446

https://www.luogu.com.cn/problem/CF1491H

看到题,发现只有减,就和势能有关。维护势能,像这种题,树形ds显然不好做,所以可以去考虑进行分块。

考虑分块。每个块记录一个 b i b_i bi? i i i 的最深而且不在同一个块的祖先的编号。

考虑动态维护,散块重构。对于大块,如果操作次数超过 n \sqrt n n ?,显然不会变(此时它的父亲已经在上一块了。)

好了,显然要询问了。我们想一想树剖我们是怎么询问lca的。如果两点不在同一条链上,那么就由深的去挑。这题同理,我们直接用块后的去跳到 b i b_i bi? 即可。

如果不在同一块,那就偏后的跳。如果同一个块,但 b i b_i bi? 不相同,则一起跳。如果相同,就是编号打的跳父亲。

在这里插入图片描述

文章来源:https://blog.csdn.net/zhangtingxiqwq/article/details/135093792
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。