P9933 [NFLSPC #6] 9.pop_book();

· · 题解

题目链接。

由于速度至多变化 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)。