题解 P5471 【[NOI2019]弹跳】

首先，观察数据范围，发现很适合一个根号算法，因此采用 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 上删掉并向上合并。这样可以方便快速找到适合的堆顶元素。 代码没得。