题解 P5471 【[NOI2019]弹跳】

2019-07-18 14:47:23


首先,观察数据范围,发现很适合一个根号算法,因此采用 kd-tree 解决问题。

但是如果我们直接建边的话,边数会达到 $O(m\sqrt n)$ 级别,约等于 $4e7$ ,显然空间开多少都不够。

但是这张图显然是有特性的:即没有负边。这很适合采用 $dijkstra$ 算法。

因此,我们不去建边,而是直接 在kd-tree上进行最短路

具体来说,我们建一个堆,和一个 kd-tree 。一开始,堆中间只有 $1$ 号点。

每轮,我们取出堆顶元素,然后利用堆顶的连边情况在 kd-tree 上打区间 $chkmin$ 标记。注意,这个标记不需要下传。

可以发现这样做无法快速更新堆中元素到 $1$ 号点距离,难以取点。不过,可以注意到,只有被更新过的点才有可能产生贡献。因此我们每次更新过后向堆中放入 kd-tree对应区间的节点 ,即一次性将整个区间都丢进去。

然后我们每次从堆中提出堆顶元素,再找到这个元素对应区间中 还没有作为起点更新过其他节点的所有节点 ,然后将这些节点放到操作序列中按序更新。

容易发现这样做的话 kd-tree 上的每个节点都只会被提出来 $1$ 次,每次更新复杂度为 $O(\sqrt n)$ ,因此总复杂度为 $O(n\log n+m\sqrt n)$ 。

顺便一提,为了更方便地提出 kd-tree 上的整个区间以及在整个区间上打 tag ,可以将 kd-tree 建成实际信息只在叶子上的样子。

为了节省时间,其实可以将更新过的节点直接从 kd-tree 上删掉并向上合并。这样可以方便快速找到适合的堆顶元素。

代码没得。