bzoj

在这里插入图片描述

bzoj 3730. 震波(动态点分治 + vector树状数组)

(自己写的动态点分治巨垃圾,常数是别人的两倍) 用动态开点线段树死活过不去,学了一波大佬用 vector 开树状数组立马就卡过去了 考虑点分树的做法,在点分树上每个点以距离为下标建一棵线段树,每次询问查询子树的贡献,再暴力向上跳合并父节点来自其它节点的贡献。 因为子树树形被破坏,在做减法时,子节点子树对父节点的贡献不能用子树维护的信息 + 连向父节点的边的贡献得到,考虑在每个节点再维护一个线段树,... »