rprp

数据结构

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 数据结构（共2篇）

Luogu [ZJOI2015]幻想乡战略游戏

显然，一棵树的带权重心最多只有两个，最少会有一个，而且在这两个点的答案一定相等。（都是带权重心当然相等）鉴于点分治的写法貌似并不太需要这样的分析，就不说了。我不会首先建出一颗点分树，然后考虑在点分树上跳儿子来保证复杂度，于是我们就需要快速算出所有点到这个重心的带权距离和。由于这题是点分树，考虑在点...

动态点分治

2020-05-05

0 375

P6329 【模板】点分树 | 震波

前言由于这篇题解思路并没有什么区别，所以这篇题解的意义在于稍稍更细致地讲下思路和卡常方法。估计也只有我常数这么大了思路第一感由于题目要查询到一个点距离为\(k\)以内的所有点的权值和，一个显然的想法就是对每个点开一个线段树维护权值和，下标维护距离，然后暴力查询。显然这是\(MLE+T...

线段树动态点分治

2020-05-06

0 657