2015年6月7日 星期日

[CF 477E] Dreamoon and Notepad

作法:

這題我是看了官方解的大概才會作的,這裡紀錄一下詳細的作法。

首先在讀入問題時,就可以把「按一次HOME」和「一路按往上/下到指定那列,再按左右調整到所求的位置」的答案算好了,後者需要一次RMQ,我是用 Sparse Table $O(1)$查詢的,因為之後也需要RMQ,用$O(1)$可以降一些複雜度。

對於官方解中的第二種情形,假設此次詢問是$(x_0,y_0),(x_1,y_1)$,其中可以假設$x_0\leq x_1$。那麼假設我們在第$x$列的時候按下了END,那麼走的步數就會是:$x_1-x_0+|y_1-min\{ a_x,...,a_{x_1}\} |+1$(注意到因為沒有按下END的情形已經在前面處理過了,所以這裡的$+1$是一定會存在的),並且$x$還要滿足$x\geq x_0$,因此此時會需要$min\{ a_x,...,a_{x_1}\}$這個東西的函數圖形。而不難知道這是一個隨著$x$變小而變小的階梯狀函數,所以考慮當$x$從$x_1$開始往左邊跑,把所有「$a_x$創新小」的點紀錄起來,具體來說那些「創新小」的點就是滿足$a_x<a_{x+1},...,a_{x_1}$的$(x,a_x)$(包含$x_1$本身)。有了這些點就可以很好的代表這個函數圖形了(之後稱這些點為這個函數的「代表」)。假設我們現在已經有了這個函數圖形(也就是這些點們),那麼可以發現我們要 minimize 的函數只和$y_1$和階梯函數的差值有關,因為這個階梯函數是單調的,所以只要找代表點們和$y_1$最接近的地方就可以了,因此就用一個 lower_bound 找出第一個$x$座標$\geq x_0$的代表是誰(假設叫$id_1$),然後從$id_1$到最後一個代表裡用一個 lower_bound 找出第一個$y$座標$\geq y_1$的代表是誰(假設叫$id_2$)(把代表點的$x$座標和$y$座標分開存就可以輕鬆 lower_bound 了),那麼就可以拿$id_2-1$和$id_2$代入上面那坨我們要 minimize 的函數裡面更新答案。這裡有可能所有代表的$y$座標都同時大於$y_1$或小於$y_1$,不過這樣的算法可以好好的處理這種情形。

但實作上總不能對每次詢問再去找出他的$x_1$造出的$min$函數的代表們,所以才離線處理所有詢問。把所有詢問按照$x_1$由小到大排序,用一個 stack 來存當此時詢問的 $x_1$ 值是 $i$ 的話他的代表們會長怎樣,那麼當詢問的$x_1$值變大的時候就不難維護這些代表們了。注意到這裡只處理了$x_0\leq x_1$的情形,當$x_0 > x_1$ 時必須略過這個詢問(因為現在這個 stack 不會是我們要的) ,這個到後面講實作的時候再來提要怎麼處理他。

再來是官方解中的第三種情形(這邊不用假設$x_0\leq x_1$),那麼此時就是先往上走到第$x$列,然後按下END(或不按),再往下走到目標列。我們先討論有按END鍵的情形,因為就算沒有按也可以按下一次(雖然沒有意義),之後再看怎樣的情形是可以不用按END鍵的,兩個都拿去更新答案就會對了。如果往上走到第$x$列,那麼總共的步數就會是$|y_1-min\{ a_x,...,a_{x_1}\} |+(x_0-x)+(x_1-x)+1$$=|y_1-min\{ a_x,...,a_{x_1}\} |-2x+x_0+x_1+1$。想像$x$從$x_0$開始慢慢變小,那麼一樣$min\{ a_x,...,a_{x_1}\}$會變小,$-2x$會變大,所以可以推得這個函數達到最小值的時候,其$x$座標一定會是那個$min$函數的一個代表。因為如果不是的話,那麼取這個點右邊的一個點,他的$min$函數值跟原本自己的一樣(因為他不是代表),但所求值中的$-2x$值變小了,因此所求函數在不是代表的數不可能達到最小值。再來想像當$x$一直變小,到有一天$min\{ a_x,...,a_{x_1}\}$ 變得$\leq y_1$時,比這個$x$小的所有數都不會讓這個函數取到最小值了,因此可以把求這個函數的最小值分為兩段來處理,一段是讓那坨$min$值$\geq y_1$的,另一段則是那坨$min$值$\leq y_1$的,由上面的推論知道第二段裡只須考慮一個點就好。對於第一段裡的代表們來說,可以把絕對值拆開,就變成$min\{ a_x,...,a_{x_1}\}-y_1-2x+x_0+x_1+1$$=(min\{ a_x,...,a_{x_1}\}-2x)+(x_0+x_1+1-y_1)$。因此我們要在$min$函數的代表們的一段區間中,詢問「代表的$y$座標扣掉兩倍的$x$座標」的最小值是多少,其中這個區間是滿足$min\{ a_x,...,a_{x_1}\} \geq y_1$且$x\leq x_0$的代表$x$們(一樣可以分別用個 lower_bound 求出)。因此在離線處理詢問維護 stack 的同時也要維護一棵線段樹,這顆線段樹用來維護的底層序列的第$i$項的值就是現在在 stack 中的第 $i$ 個代表的$y$座標扣掉兩倍$x$座標的值。那麼當把一個東西 push 進 stack 的時候就等於修改這棵線段樹的底層序列的某個值, pop 的時候則什麼都不用作,這樣就能得到上述函式的最小值了。

接下來還要處理不用按END的情形,還有被分出來的$min$值$\leq y_1$的那個代表。先看前者,既然不用按END,那麼代表此時是從第$x_0$列往上走到第$x$列,然後直接往下走回第$x_1$列,並且我們需要 minimize 的式子和剛才那條幾乎一樣,兩式只有差$1$,所以可以套用剛才的一些結果。在這裡分成兩種情形來看,首先是$x_0\leq x_1$時,由剛才的結論可知最佳解$x$一定是一個代表,那麼此時就必須滿足$a_x\leq y_0$,又因為$a_x$是個代表,所以可以寫成$min\{ a_{x_1},...,a_x \} \leq y_0$。反過來當$x$滿足他是一個代表,並且$a_x\leq y_0$時,不難得出從$x_0$往上走到$x$時其橫座標會停留在$a_x$,所以此時不用按END。再來則是$x_0\geq x_1$時,那麼當從$x_0$往上走的時候,會先經過$x_1$,此時其橫座標會是$min\{ y_0,a_{x_1},...,a_{x_0} \} $,並且由一樣的理由可以得到此時$x$必須滿足$a_x\leq min\{ y_0,a_{x_1},...,a_{x_0} \} $,且他也是充要條件(這就可以用之前建好的 Sparse Table 來算)。因此這樣就得到了「不用按END」的那些列的範圍了,只要再用一次 upper_bound 就可以得到此時$x$必須$\leq $某個值,再和前面「不考慮是否要按END」時得到的區間交集,就知道要對線段樹的哪一段 query 了,然後拿上面的式子的值去更新答案(但此時是少了$+1$的)。

最後則是被分出來的$min$值$\leq y_1$的那個代表,由上面的條件容易確認當$x$等於他時到底要不要按END,一樣拿他去更新答案即可。

到這裡我們解決了官方解中的第一、三種情形,還有第二種情形的一半,接下來則是要把整個$a$數列反轉,把每一個詢問也反轉(原本的$x_0,x_1$變成$n+1-x_0,n+1-x_1$),再重做一次上述過程就可以了(Sparse Table 要重建,線段樹則不用理他),這樣就能把官方解中剩餘的情形(二的一半和四)補完了。

code :



#include<bits/stdc++.h>
#define ABS(x) ((x)>0 ? (x) : (-(x)))
using namespace std;
const int maxn=400000+10 , LOG=int(log2(maxn)+1) ;
 
int n,a[maxn] ;
int rmq[LOG][maxn],log_t[maxn] ;
inline void build_rmq()
{
    for(int i=0;(1<<i)<=n;i++) for(int j=1;j+(1<<i)-1<=n;j++)
        rmq[i][j]=(i ?
        min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]) : a[j]) ;
}
inline int rmq_query(int l,int r)
{
    int t=log_t[r-l+1] ;
    return min(rmq[t][l],rmq[t][r-(1<<t)+1]) ;
}
 
int ST[4*maxn] ;
void modify(int L,int R,int id,int pos,int val)
{
    if(L==R){ST[id]=val ; return ;}
    int mid=(L+R)/2 ;
    if(pos<=mid) modify(L,mid,2*id,pos,val) ;
    else modify(mid+1,R,2*id+1,pos,val) ;
    ST[id]=min(ST[2*id],ST[2*id+1]) ;
}
int query(int l,int r,int L,int R,int id)
{
    if(l==L && r==R) return ST[id] ;
    int mid=(L+R)/2 ;
    if(r<=mid) return query(l,r,L,mid,2*id) ;
    else if(l>mid) return query(l,r,mid+1,R,2*id+1) ;
    else return min(query(l,mid,L,mid,2*id),
                    query(mid+1,r,mid+1,R,2*id+1)) ;
}
 
int ans[maxn],sta[maxn],stid[maxn] ;
int size ;
void process_query(int x0,int y0,int x1,int y1,int qid)
{
    if(x1>=x0)
    {
        int id1=lower_bound(stid,stid+size,x0)-stid ;
        int id2=lower_bound(sta+id1,sta+size,y1)-sta ;
        if(id2<size) ans[qid]=min(ans[qid],x1-x0+1+sta[id2]-y1) ;
        if(id2>id1) ans[qid]=min(ans[qid],x1-x0+1+y1-sta[id2-1]) ;
    }
    int id1=lower_bound(sta,sta+size,y1)-sta ; /// x >= id1
    int id2=upper_bound(stid,stid+size,x0)-stid-1 ; /// x <= id2
 
    if(id1<=id2)
        ans[qid]=min(ans[qid],query(id1,id2,0,n-1,1)-y1+x0+x1+1) ;
 
    int val=y0 ;
    if(x0>x1) val=min(val,rmq_query(x1,x0)) ;
    int id3=upper_bound(sta,sta+size,val)-sta-1 ;
    id3=min(id3,id2) ;
    if(id1<=id3)
        ans[qid]=min(ans[qid],query(id1,id3,0,n-1,1)-y1+x0+x1) ;
 
    if(id1-1<=id2 && id1) ans[qid]=min(ans[qid],
        (y1-sta[id1-1])-2*stid[id1-1]+x0+x1+(val<sta[id1-1])) ;
}
 
struct P{int x0,y0,x1,y1,id;};
void process(vector<P> *v)
{
    size=0 ;
    for(int i=1;i<=n;i++)
    {
        while(size && sta[size-1]>=a[i]) size-- ;
        modify(0,n-1,1,size,a[i]-2*i) ;
        sta[size]=a[i] ; stid[size++]=i ;
        for(auto it : v[i]) process_query(it.x0,it.y0,it.x1,it.y1,it.id) ;
    }
}
 
vector<P> qu[2][maxn] ;
main()
{
    log_t[0]=log_t[1]=0 ;
    for(int i=2;i<maxn;i++) log_t[i]=log_t[i/2]+1 ;
 
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    int Q ; scanf("%d",&Q) ;
 
    build_rmq() ;
    for(int i=1;i<=Q;i++)
    {
        int x0,y0,x1,y1 ; scanf("%d%d%d%d",&x0,&y0,&x1,&y1) ;
        qu[0][x1].push_back((P){x0,y0,x1,y1,i}) ;
        qu[1][n+1-x1].push_back((P){n+1-x0,y0,n+1-x1,y1,i}) ;
        ans[i]=ABS(x0-x1)+y1+1 ;
        if(x0==x1) ans[i]=min(ans[i],ABS(y0-y1)) ;
        else
        {
            int mi=(x0>x1 ? rmq_query(x1,x0) : rmq_query(x0,x1)) ;
            mi=min(mi,y0) ;
            ans[i]=min(ans[i],ABS(x0-x1)+ABS(mi-y1)) ;
        }
    }
    process(qu[0]) ;
    for(int i=1;n+1-i>i;i++) swap(a[i],a[n+1-i]) ;
    build_rmq() ;
    process(qu[1]) ;
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]) ;
}
 

沒有留言:

張貼留言