自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:53:08，当前版本为作者最后更新于2023-12-17 21:04:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接。

由于速度至多变化 $n$ 次，所以路程关于时间的函数是一个至多 $n$ 段的分段函数，且每一段都是线段。如果能求出每一段线段两端的坐标，就可以快速回答询问。基于此，有两种维护方式。

解法一

因为 A 只会跟着经过他的速度最快的人移动，所以只要一个人被超越，他就一定不产生影响。

使用平衡树维护所有人的相对位置。一旦某两个人的相对位置发生改变，那么一定有一个人被删除。

按照时间顺序模拟，平衡树上二分算出加入的人插入的位置，以及他和相邻两个人什么时候会撞在一起，将两个时刻加入优先队列。不断取出最小的相邻两个人撞在一起的时刻，判断事件是否会发生（因为其中一个人已经和其他人撞起来了），以及发生时刻是否小于下一个人加入的时间。将速度较慢（相撞时在前面）的人删除，加入速度较快的人和新的在他前面的人相撞的时间。

模拟过程中容易计算 A 在每个时刻的总移动距离。

时间复杂度 $\mathcal{O}(n\log n)$。

解法二

解法一需要平衡树，写起来很麻烦。

换一种思路，断环成链，将操场视为一条数轴。数轴上的位置 $x$ 表示 A 从起点出发移动 $x$ 单位距离。于是，加入一个人时，可以根据他加入的位置和 A 当前的位置算出他在数轴上的位置，于是他在数轴上的位置关于时刻 $t$ 可以写成一条射线 $kt + b$（$t\geq t_i$），其中 $k$ 是他的速度。由于加入一个人之后不会涉及到 $t_i$ 之前的时刻，于是可认为射线就是直线。

查询 A 的位置相当于查询若干条直线在某个点处的最大值，使用李超线段树维护即可。注意后加入的直线会影响之前的时间，所以依然需要离线回答询问。

时间复杂度 $\mathcal{O}(n\log n)$。