rprp

分类

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

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 668人学习

全部文章（共3篇）

Luogu P2056 [ZJOI2007]捉迷藏

动态点分治先建出一颗点分树，然后维护。对于每一个点维护两个堆，一个堆维护子树内所有点到分治父节点的距离最大值，一个堆维护一个点所有子树的第一个堆的最大值，再全局维护一个堆取所有分治重心的答案的最大值即可。代码细节感人。。。一个比较有用的trick就是用两个大根堆实现可删除的堆但是要开O2 ...

堆动态点分治

2020-05-04

0 398

Luogu [ZJOI2015]幻想乡战略游戏

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

动态点分治

2020-05-05

0 375

P6329 【模板】点分树 | 震波

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

线段树动态点分治

2020-05-06

0 657