自动搬运

查看原文

来自洛谷，原作者为

	Diu 上分！

搬运于2025-08-24 22:47:02，当前版本为作者最后更新于2023-09-19 20:29:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $n,m$ 同阶。

最短路的边数是 $O(k^2)$ 的，基于这个就很多做法都无法通过。

因此考虑减少边的数量。

对于每个点 $(x,y)$，考虑有多少条边是有用的。

我们以该点为原点构建直角坐标系，对于在坐标轴上的点，在四个方向分别取最近的点。剩下的分成每个象限讨论。

有一个结论：对于一个象限，只保留切里雪夫距离最近的所有点即可。证明如下：

假设当前点 $O(0,0)$，其中一个最近的点为 $P(x,y)$，不妨设 $0<y\le x$，我们证明对于所有 $A(a,b),a>0,b>0,\max(a,b)>x$，点 $O$ 到点 $A(a,b)$ 这条边一定不优。

若 $a>x,b>y$，那么 $OP,AP<OA$，因为都是 $2^x$ 的形式，所以有 $OP+AP\le OA$。

否则有 $a\in[1,x],b>x$，$OP=2^x$。若 $x-a\ge b-y$，那么 $AP=2^{x-a}$,$OP+AP<2^{x+1}\le OA$；否则 $AP=2^{b-y},OA=2^b$，同理因为 $y>0$，所以 $OP+AP=2^{b-y}+2^x\le 2^b=OA$。

结论得证。

因为是切里雪夫距离，所以对于一个点有效的出边实际上是 $O(1)$ 段横着或者竖着的线段，可以考虑线段树优化建图，这样边数变成 $O(k\log k)$。

如果直接跑 Dijkstra，用 bitset 维护高精度，复杂度是 $O(\dfrac{nk\log^2 k}{\omega})$。听说能过。

但是有一个 well-known 的 trick，当线段树优化建图和堆优化 Dijkstra 同时出现的时候，可以直接线段树优化 Dijkstra 做到少一个 $\log$。

具体是说，维护一棵线段树，支持区间取 $\min$，全局找到没被标记的点得最值，标记一个点。只要支持打 tag 就可以实现这个操作。复杂度变成 $O(\dfrac{nk\log k}{\omega})$，这个似乎就是官方题解。

但是我们还能优化，还有一个 well-known(?) 的 trick，我们采用 CF464E 的方法维护二进制数。我们实际上对于二进制数只有三种操作：比较；加上 $2^i$；赋值。我们采用主席树维护二进制数，记录区间哈希值和区间是否为全 $1$。赋值简单，比较采用二分哈希找 lcp，加上 $2^i$ 实际上是先找到从第 $i$ 为开始的极长连续的 $1$，然后这一段赋值为 $0$，再把这一段的上一位修改为 $1$。找连续 $1$ 还是可以二分，而区间赋值为 $0$ 有一个方法是说我们建立一些常节点 $t_i$ 表示一个长度为 $i$ 的全 $0$ 区间，当主席树上一个长度为 $i$ 的区间赋值为 $0$ 的时候直接让它的父亲指向 $t_i$ 即可。

这样比较修改都可以在 $O(\log n)$ 的时间内做完高精度的操作，把 bitset 的 $O(\dfrac n{\omega})$ 变成 $O(\log n)$，因此复杂度优化为 $O(k\log n\log k)$。分析一下空间复杂度：比较操作并不会新开空间，只有加 $2^i$ 会增加 $O(\log n)$ 的空间，而实际上总共只有 $O(k)$ 次操作，所以总空间是 $O(k\log n)$，但是由于每个象限都要维护两个，每一侧坐标轴上也都有一个，所以带一个 $12$ 的常数。

到这里就差不多做完了，还有一件事，你需要支持对于每个点找到每个象限切里雪夫最近的距离。一个比较好的做法是时间 $O(k\log^2 n+n\log n)$ 空间 $O(n\log n)$ 二分主席树做法。

实现看似难写，实则可能不难写，每个部分封装好的话还是好写的。

code，大概 8k，目前最优解。