[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]) ;
}