AquaRio 的博客

AquaRio 的博客

题解 P3103 【[USACO14FEB]登机Airplane Boarding】

posted on 2019-10-12 00:13:05 | under 题解 |

Description

有 $n$ 头牛,排在 $−n+1,...,0$ 的位置上。从左往右就座,有走路的时间,有原地放东西的时间。牛不能越过另一头牛。求时间。

Solution

先看第 $n$ 只牛,他在 $t=0$ 的时候位于 $x=0$ 的位置,并且在时间 $t=S_n$ 时走到自己位置, $t=S_n + T_n$ 时坐下。而这就带给了第 $n-1$ 只牛一个限制:必须要等到时间为 $t=S_n + T_n+1$ 时他才有办法走到 $S_n$ 。

所以当我们处理每只牛的时候,假设对这只牛的限制为 $(a_1,b_1),...,(a_r,b_r)$ ,其中 $(a,b)$ 代表至少要等到 $b$ 秒时才可以走到 $a$ 位置。

那么这只牛走到目的地的时间就会是: $\max\{b_i+(S - a_i)\}$ ,其中 $a_i$ 满足 $a_i <= S$ 。

也就是我们会需要查询在所有第一个坐标 $<= S$ 的限制中, $b - a$ 最大的数是多少。

$O(n^2)$ 的做法很好想,直接大力枚举。

我们仔细思考,发现,如果有两个限制 $(a,b)$ 和 $(c,d)$ ,满足 $c > a$ 且 $d-c < b-a$ ,那么 $(c,d)$ 这个限制就废掉了。

所以每次加入一个新的限制 $(a,b)$ 时要再把所有废掉的 $(c,d)$ 都去掉。

虽然看起来还是 $O(n^2)$ 的,但是我们可以发现可以用treap维护所有的限制。

打一个FHQ Treap,对每个限制都记录他的 $a$ 值和 $b-a$ 值,还有这棵子树中 $b-a$ 的最大值。询问的时候只要把 $a <= S_i$ 的那一部分切下来就好了,然后把右子树 $b-a$ 值小的子树切掉。最后再把更新完的子树合并起来即可。

代码请看blog