题目大意

有 $N$ 个世界，世界 $i$ 初始位于 $(i, A_i)$，以速度 $i$ 单位/秒向 $y$ 轴负方向运动。当两个世界的 $y$ 坐标相同时（可能在非整数时刻），它们可以互相传送。对于每个世界 $i$ 的奶牛，求到达世界 $Q_i$ 的最短时间，输出分数形式或 $-1$（如果不可达）。

问题分析

运动模型

世界 $i$ 在时刻 $t$ 的坐标为：

• $x = i$（固定）
• $y = A_i - i \cdot t$

同步条件

两个世界 $i$ 和 $j$（$i < j$）在时刻 $t$ 同步的条件：

$$A_i - i \cdot t = A_j - j \cdot t$$

解得：

$$t = \frac{A_i - A_j}{i - j}$$

重要性质：同步时间 $t$ 必须为非负数。

问题转化

将问题建模为图论问题：

• 节点：各个世界
• 边：如果世界 $i$ 和 $j$ 可以在某个非负时刻同步，则添加无向边，边权为同步时间 $t$
• 目标：对于每个 $i$，求从节点 $i$ 到节点 $Q_i$ 的最短路径（路径权值为边权最大值）

算法设计

方法一：直接图论建模（小数据）

核心思想：显式构建完整图，使用最短路算法。

步骤：

1. 对于每对世界 $(i, j)$，计算同步时间 $t = \frac{A_i - A_j}{i - j}$
2. 如果 $t \geq 0$，添加边 $(i, j)$，权值为 $t$
3. 对每个询问，运行Dijkstra算法求最短路

复杂度：$O(N^2 \log N)$，仅适用于 $N \leq 10^3$

方法二：凸包优化

关键观察：世界的运动轨迹是直线 $y = A_i - i \cdot t$，在 $t-y$ 平面中，这些直线在 $t=0$ 时截距为 $A_i$，斜率为 $-i$。

凸包技巧：

1. 将世界按 $x$ 坐标（即编号 $i$）排序
2. 维护一个凸包，包含可能产生关键同步事件的世界
3. 对于每个世界，只需要考虑与凸包中世界的同步

具体实现：

• 上凸壳：用于处理从编号小的世界向编号大的世界传送
• 下凸壳：用于处理从编号大的世界向编号小的世界传送
• 在凸壳上二分查找最优的传送路径

方法三：离线处理 + 并查集

核心思想：按时间顺序处理同步事件，维护连通性。

步骤：

1. 预处理所有可能的同步事件 $(i, j, t)$，按 $t$ 排序
2. 使用并查集维护世界的连通性
3. 当处理到时间 $t$ 时，合并相应的世界
4. 对于每个询问，记录两个世界首次连通的时间

优化：使用按秩合并的并查集，可以记录合并时间

方法四：倍增法

核心思想：对于每个世界，预处理通过 $2^k$ 次传送能到达的最远世界和所需时间。

步骤：

1. 对于每个世界 $i$，计算直接传送可以到达的世界集合
2. 预处理倍增数组 $next[i][k]$ 和 $time[i][k]$
3. 对于查询 $(i, Q_i)$，使用倍增法求解最短时间

关键洞察

图论性质

• 边权是同步时间，路径的权值是路径上边权的最大值
• 这是一个最小化最大边权的最短路问题
• 可以使用类似Kruskal算法的思想：按边权从小到大加边

几何性质

• 在 $t-y$ 平面中，每个世界的轨迹是一条直线
• 两条直线 $y = A_i - i t$ 和 $y = A_j - j t$ 的交点横坐标就是同步时间
• 凸包上的世界代表了"可见"的传送机会

实现细节

分数处理

• 同步时间 $t = \frac{A_i - A_j}{i - j}$ 需要化为最简分数
• 使用辗转相除法求最大公约数
• 注意正负号和分母的正负性

数据结构选择

• 凸包维护：使用栈维护凸壳点
• 查询处理：在凸壳上二分查找
• 分数比较：避免浮点数，使用交叉相乘比较

复杂度分析

凸包方法

• 预处理：$O(N \log N)$ 排序和构建凸包
• 每个查询：$O(\log N)$ 在凸包上二分
• 总复杂度：$O(N \log N)$

并查集方法

• 事件排序：$O(N \log N)$
• 并查集操作：$O(N \alpha(N))$
• 总复杂度：$O(N \log N)$

算法选择建议

• $N \leq 10^3$：方法一（简单直接）
• $N \leq 2 \times 10^5$：推荐凸包方法或并查集方法
• 实现难度：凸包方法思维难度高但代码简洁，并查集方法思维直接但实现稍复杂

总结

本题的核心在于将物理运动问题转化为计算几何和图论问题，利用凸包性质优化边数，从而在大规模数据下高效求解。关键在于理解世界的运动轨迹在 $t-y$ 平面中的几何性质，以及如何利用这些性质减少需要考虑的传送机会。