[USACO 2014 Gold] Airplane Boarding

作法：

先看第 n 隻牛，他在時間 0 的時候位於 x=0 ，並且在時間 S[ n ] 時走到自己位置， S[ n ] + T[ n ] 時坐下。而這就帶給了第 n-1 隻牛一個限制：必須要等到時間為 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 最大的數是多少。所以現在可以得到這樣的算法：按照 n ~ 1 的順序處理每隻牛，一開始的限制就只有 ( 0 , 0 ) ，然後對於每個正在處理的牛 i ，掃一遍目前所有的限制，把 a 值 <= S[ i ] 的限制們的 b-a 值拿去更新最大值，算出這隻牛坐好的時間 U[ i ] ，並且這會代表第 i-1 隻牛至少要等到 U[ i ] +1 才可以走到 S[ i ] ，也就是多把 ( S[ i ] , U[ i ] +1 ) 加入限制中。但還要注意到的是，如果 ( a , b ) 滿足 a <= S[ i ] ，代表第 i 隻牛至少要到時間 b 才可以走到 a 位置，那麼這件事對第 i-1 隻牛來說就會變成：他至少要到時間 b 才可以走到 a-1 位置，因為他會被第 i 隻牛擋住，而對於那些 a > S[ i ] 的限制們則不用更新。所以我們必須要在算完 i 的答案時，對所有 a <= S[ i ] 的限制們都更新一次，這樣就得到了 O(n^2) 的演算法。

至於要如何優化成O(nlogn) ，首先要注意到：如果有兩個限制 ( a , b ) 和 ( c , d ) ，滿足 c > a 且 d-c < b-a ，那麼 ( c , d ) 這個限制就廢掉了，因為當 c <= S[ i ] 時 a 必定也 <= S[ i ] ，他永遠不會比 ( a , b ) 更好，也就是在我們維護的限制們裡，當 a 遞增時 b-a 也是遞增的，所以每次加入一個新的限制 ( a , b ) 時要再把所有廢掉的 ( c , d ) 都砍掉。雖然這個觀察還是會得到O(n^2) 算法，但是這樣就會發現可以用 treap 維護所有的限制。使用分裂合併式的 treap ，並且對每個限制都記錄他的 a 值和 b-a 值，還有這棵子樹中 b-a 的最大值，而且我們會需要區間加值的動作，所以會需要再記個 tag 值。當要詢問的時候只要把 a <= S[ i ] 的那一部分切下來問問就好了，並且在砍掉不必要的 ( c , d ) 時，可以很方便的直接從剛剛切完得到的右子樹中，直接把 b-a 值太小的節點都切掉( 因為當 a 遞增時 b-a 也遞增，所以單看 b-a 的話他也還是一個treap )，並且在「對於 a<=S[ i ] 的限制，都把 a 值減一」的操作時只要對左子樹打個標記就好了，最後再把領個更新完的子樹黏起來即可。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
struct node
{
    node *l,*r ;
    int x,y ;
    int val,tag,fix ;
    node(int _x,int _y)
    {
        l=r=NULL ;
        x=_x ; y=_y ;
        val=y ;
        tag=0 ;
        fix=rand() ;
    }
};
 
void push(node *u)
{
    if(!u || !u->tag) return ;
    if(u->l)
    {
        u->l->x -= u->tag ;
        u->l->y += u->tag ;
        u->l->tag += u->tag ;
        u->l->val += u->tag ;
    }
    if(u->r)
    {
        u->r->x -= u->tag ;
        u->r->y += u->tag ;
        u->r->tag += u->tag ;
        u->r->val += u->tag ;
    }
    u->tag=0 ;
}
 
void pull(node *u)
{
    if(!u) return ;
    u->val=u->y ;
    if(u->l) u->val=max(u->val,u->l->val) ;
    if(u->r) u->val=max(u->val,u->r->val) ;
}
 
node *merge(node *a,node *b)
{
    if(!a || !b) return a ? a : b ;
    if(a->fix < b->fix)
    {
        push(a) ;
        a->r=merge(a->r,b) ;
        pull(a) ;
        return a ;
    }
    else
    {
        push(b) ;
        b->l=merge(a,b->l) ;
        pull(b) ;
        return b ;
    }
}
 
void split(node *u,node *&a,node *&b,int k)
{
    if(!u) { a=b=NULL ; return ; }
    push(u) ;
    if(u->x <= k)
    {
        a=u ;
        split(u->r,a->r,b,k) ;
        pull(a) ;
    }
    else
    {
        b=u ;
        split(u->l,a,b->l,k) ;
        pull(b) ;
    }
}
 
void split2(node *u,node *&a,node *&b,int k)
{
    if(!u) { a=b=NULL ; return ; }
    push(u) ;
    if(u->y <= k)
    {
        a=u ;
        split2(u->r,a->r,b,k) ;
        pull(a) ;
    }
    else
    {
        b=u ;
        split2(u->l,a,b->l,k) ;
        pull(b) ;
    }
}
 
int p[maxn],t[maxn],n ;
node *root=NULL ;
main()
{
    if(fopen("boarding.in","r"))
    {
        freopen("boarding.in","r",stdin);
        freopen("boarding.out","w",stdout);
    }
    srand(time(NULL)) ;
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&t[i]) ;
 
    int ans=0 ;
    root=merge(root,new node(0,0)) ;
    for(int i=n;i>=1;i--)
    {
        node *a,*b,*c ;
        split(root,a,b,p[i]) ;
        int val=a->val+p[i]+t[i] ;
        ans=max(ans,val) ;
        a->tag++ ; a->x-- ; a->y++ ; a->val++ ;
        split2(b,b,c,val+1-p[i]) ;
        root=merge(merge(a,new node(p[i],val+1-p[i])),c) ;
    }
    printf("%d\n",ans) ;
}