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

**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](http://39.105.95.125/index.php/archives/433/)