势能相关难维护的用分块——分块过程维护跨块的:CF1491H / P7446
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? 不相同,则一起跳。如果相同,就是编号打的跳父亲。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!