[CF 533D] Landmarks

作法：

首先把每個柱子的強度都乘以 $2$ （包括答案），這樣對於一根柱子來說，他會倒塌若且唯若他的強度小於左右兩跟柱子的距離，也就是他必須支撐從他到他左邊柱子的天花板，還有從他到他右邊柱子的天花板，這樣可以讓之後的處理跟理解比較方便。假設我們已經在某個地方放上一個柱子，使得最後沒有全部倒塌的話，假設現在留下來的柱子為原本柱子們的第 $a_1 , ... , a_k$ 根，且新加的柱子落在 $a_i$ 和 $a_{ i+1 }$ 之間，那麼這代表當我們單獨看 $a_1$ ~ $a_i$ 的時候， $a_1$ ~ $a_{ i-1 }$ 均不會倒塌，並且 $a_i$ 除了支撐 $a_{ i-1 }$ ~ $a_i$ 的天花板以外，至少還要有力氣支撐他右邊的天花板，而這對於 $a_{ i+1 } ~ a_k$ 來說也一樣。並且如果新加的柱子和 $a_i$ 的距離為 $x$ ，和 $a_{ i+1 }$ 的距離為 $y$ ，那麼必須要有 $a_i$ 除了支撐左邊以外，能多支撐的天花板長度 $\geq x$ ，還有 $a_{ i+1 }$ 除了支撐右邊以外，能多支撐的天花板長度 $\geq y$ ，兩式加起來可以得到 $a_i$ 可以多支撐的長度加上 $a_{ i+1 }$ 可以多支撐的長度 $\geq a_i$ 和 $a_{ i+1 }$ 的距離。因此這啟發了我們可以對於每根柱子，都計算他的「可多支撐右邊的強度」。更嚴謹的來說，對於每個 $i$ ，考慮所有的子序列 $b_1 , ... , b_r = i$ ，並且滿足如果只剩下 $b_1$ ~ $b_r$ 這些柱子時，他們都不會倒塌，那麼 $i$ 的「可多支撐右邊的強度」就是所有這樣的子序列的 $s[ b_r ] - ( pos[ b_r ] - pos[ b_{ r-1 } ] )$ 的最大值。其中 $s[ i ]$ 代表第 $i$ 根柱子的強度， $pos[ i ]$ 代表第 $i$ 根柱子的位置。

記上面所說的要算的東西為 $dp1[ i ]$ ，那麼首先可以想到一個 $O( n^2 )$ 的顯然的作法，就是在算 $i$ 的時候枚舉要放在他左邊的柱子是哪一根就可以了。而如果我們反過來看，假設現在已經算完 $dp1[ i ]$ 了，那麼對於所有位置小於等於 $pos[ i ] + dp1[ i ]$ 的柱子來說，都可以從 $i$ 轉移過去。並且當 $i$ 可以轉移到 $j$ 的時候，就代表 $dp1[ j ]$ 就必須和 $s[ j ] - pos[ j ] + pos[ i ]$ 取 max 。注意到這個東西只和 $pos[ i ]$ 有關，因此這樣就可以用線段樹來計算 $dp1$ 陣列的值了：每當算完 $dp1[ i ]$ 時，找出他最遠可以轉移到哪根柱子，假設為 $i2$ 好了，那麼就把 $i+1$ ~ $i2$ 的每個值都和 $pos[ i ]$ 取 max ，之後要計算 $dp1[ j ]$ 的時候，只要在線段樹上查詢這個點的值，再把他加上 $s[ j ] - pos[ j ]$ 就可以了。

因此用一樣的方法也可以算出每根柱子的「可多支撐左邊的強度」，把他記為 $dp2[ i ]$ 。這個值的定義和 $dp1$ 很類似，不過這次取的則是形如 $b_1 = i , b_2 , ... , b_r$ 的子序列（他和 $dp1$ 一樣都是第一段中提到的一個重要的值）。有了 $dp1$ 和 $dp2$ 之後就可以求解了，首先判斷是否不用加新的柱子也不會全部倒塌，而這只要存在一個 $i$ ，使得 $dp1[ i ] \geq pos[ n+1 ] - pos[ i ]$，就代表可以直接從第 $i$ 根柱子接到最後一根，此時答案是 $0$ 。否則我們要找的是：對於所有的 $i < j$ ，如果 $dp1[ i ] + dp2[ j ] \geq pos[ j ] - pos[ i ]$ ，並且 $dp1[ i ] > 0 , dp2[ j ] > 0$，那麼 $pos[ j ] - pos[ i ]$ 就會是一個可行的答案，只要把他放在 $pos[ i ]$ 和 $pos[ j ]$ 中間的適當位置就可以了。將上式移項得 $dp1[ i ] + pos[ i ] \geq pos[ j ] - dp2[ j ]$ ， 這啟發了我們可以從右到左枚舉 i ，並且對於可能的右端點 $j$ 們維護一個二元組的 set ： $( pos[ j ] - dp2[ j ] , j )$ ，因為當如果有另外一個 $j2$ 滿足 $pos[ j2 ] - dp2[ j2 ] \geq pos[ j ] - dp2[ j ]$ ，並且 $j2 \geq j$ ，那麼 $j2$ 的二元組就廢掉了，之後不可能成為任何左端點的答案，因此這個 set 裡維護的是第一個值遞增時第二個值遞減的二元組，並且在詢問 $i$ 的答案時只要用個 lower_bound 找 $pos[ j ] - dp2[ j ]$ 值最大且滿足上述條件的二元組就可以了。

另外官方解好像和我的作法一樣，但他把每個步驟都從 $O( nlogn )$ 優化成 $O( n )$ 了，不過我還沒仔細研究他是怎麼做的。

code :

#include<bits/stdc++.h>
#define INF 1100000000
using namespace std;
const int maxn=100000+10 ;
 
int ST[4*maxn] ;
void build(int l,int r,int id)
{
    ST[id]=-INF ;
    if(l==r) return ;
    int mid=(l+r)/2 ;
    build(l,mid,2*id) ;
    build(mid+1,r,2*id+1) ;
}
 
void Setmax(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R){ ST[id]=max(ST[id],val) ; return ; }
    int mid=(L+R)/2 ;
    if(r<=mid) Setmax(l,r,L,mid,2*id,val) ;
    else if(l>mid) Setmax(l,r,mid+1,R,2*id+1,val) ;
    else Setmax(l,mid,L,mid,2*id,val) ,
        Setmax(mid+1,r,mid+1,R,2*id+1,val) ;
}
 
int query(int L,int R,int id,int pos)
{
    if(L==R) return ST[id] ;
    int mid=(L+R)/2 ;
    if(pos<=mid) return max(ST[id],query(L,mid,2*id,pos)) ;
    else return max(ST[id],query(mid+1,R,2*id+1,pos)) ;
}
 
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? y<rhs.y : x<rhs.x ;
    }
};
 
set<P> st ;
void insert(const P &p)
{
    st.insert(p) ; auto it=st.find(p) ;
    bool keep=1 ;
    if(it!=st.begin())
    {
        it-- ;
        if(p.y >= it->y) keep=0 ;
        it++ ;
    }
    if(!keep){st.erase(it) ; return ;}
    while(1)
    {
        auto it2=it ; it2++ ;
        if(it2!=st.end() && it2->y >= p.y) st.erase(it2) ;
        else break ;
    }
}
 
int pos[maxn],s[maxn] ;
int dp1[maxn],dp2[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=0;i<=n+1;i++) scanf("%d",&pos[i]) ;
    for(int i=1;i<=n;i++) scanf("%d",&s[i]) , s[i]*=2 ;
 
    build(1,n,1) ;
    Setmax(1,n,1,n,1,pos[0]) ;
    for(int i=1;i<=n;i++)
    {
        dp1[i]=(s[i]-pos[i])+query(1,n,1,i) ;
        if(dp1[i]<=0) continue ;
        int id=upper_bound(pos+1,pos+n+2,pos[i]+dp1[i])-pos-1 ;
        if(id==n+1) {printf("0\n") ; return 0;}
        if(id>i) Setmax(i+1,id,1,n,1,pos[i]) ;
    }
 
    build(1,n,1) ;
    Setmax(1,n,1,n,1,-pos[n+1]) ;
    for(int i=n;i>=1;i--)
    {
        dp2[i]=(s[i]+query(1,n,1,i))+pos[i] ;
        if(dp2[i]<=0) continue ;
        int id=lower_bound(pos+1,pos+n+2,pos[i]-dp2[i])-pos ;
        if(id<i) Setmax(id,i-1,1,n,1,-pos[i]) ;
    }
 
    int ans=pos[n+1]-pos[0] ;
    for(int i=1;i<=n;i++)
    {
        if(dp1[i]>0) ans=min(ans,pos[n+1]-pos[i]) ;
        if(dp2[i]>0) ans=min(ans,pos[i]-pos[0]) ;
    }
 
    for(int i=n;i>=1;i--)
    {
        auto it=st.upper_bound((P){dp1[i]+pos[i],INF}) ;
        if(it!=st.begin() && dp1[i]>0)
            it-- , ans=min(ans,pos[it->y]-pos[i]) ;
        if(dp2[i]>0) insert((P){pos[i]-dp2[i],i}) ;
    }
    printf("%.4f\n",ans*1.0/2) ;
}