题解 ROI 2018 D1T4 Quantum teleportation

· · 题解

设 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，目前最优解。