[HOJ 289][IOI 2013] Wombats

作法：

這題我也是查解才會做的。因為我們需要從第 0 排到第 R-1 排的 C*C 個答案的陣列，而這個答案陣列可以從 [ 0 , mid ] 的答案和 [ mid , R-1 ] 的答案算出來，所以就用一個線段樹，如果一個節點代表的區間是 [ l , r ] ，那麼這個節點就是紀錄第 l 到第 r 排的所有 C*C 個答案。那麼當我要用 [ l , mid ] 和 [ mid , r ] 的答案合併成 [ l , r ] 的答案時，最原始的方法就是對每個第 l 排的位置和第 r 排的位置都枚舉最佳路徑經過第 mid 排的哪個位置，這樣合併的時間是 O(C^3) ，並且當在修改的時候需要合併 log R 的線段樹上的區間，會TLE掉。但其實只要注意到他的最佳位置其實是有某種遞增性的，就是如果第 l 排的第 i 個到第 r 排的第 j 個中間經過的點的最佳位置是 X ，第 i+1 個到第 j+1 個中間經過的點的最佳位置是 Y ，那麼第 i 個到第 j+1 個中間的最佳位置就會在 X 和 Y 之間。大概可以感受到最佳解不會跑到外面，不然直接把兩條路徑交換會讓 i 到 j 的最佳路徑 ( 或 i+1 到 j+1 的最佳路徑 ) 不再是最佳路徑，就矛盾了。所以我們只要先 O(C^2) 算出第 i 個到第 i 個的最佳解和最佳位置，剩下的所有答案就可以用上面的方法在O(C^2)的時間內算出來，所以線段樹的兩個子節點的合併可以做到O(C^2)。這好像叫四邊形優化，但我沒有仔細讀過他在講甚麼QQ。

所以我們只要能算出葉節點的答案就好了( 葉節點的寬度都只有 1 )。所以現在等於是有 2 * C 個點，排成矩形的形狀，並且之間有連一些邊，要求上面C個的任意一點到下面C個的任意一點中間經過的最少數量，而這可以用DP做，考慮對每個上面的點都做一次到下面C個點的類似最短路的算法，並且因為他是特殊圖，可以做到O(C) ( 掃過來再掃過去XD )，所以計算葉節點的複雜度也是O(C^2)。

但這樣會發現線段樹必須開 10000*100*100 的陣列，會MLE掉，所以線段樹不能建得太深，就是先定好一個 K 值，到了線段樹的節點的區間長度 <= K 的時候就直接做這個區間的答案，不要到最底層才做，這樣可以節省記憶體，但會讓速度變慢。所以在葉節點的時候的計算答案的複雜度其實會變成 O(C^2 * len ) ，其中 len 是區間的長度。看網路上的題解是取 K = 15 ，所以就取跟他一樣的了。

（附上丁安立的精妙（？）解說： http://alt.twbbs.org/?p=3687 ）

code :

#include<bits/stdc++.h>
#define INF 1500000000
using namespace std;
const int maxn=5000+10 , maxc=100+2 , KK=15 ;
 
int n,m,ST[2000][maxc][maxc] ;
 
int dis[maxc] ;
void sweep_hor(int a[maxc],int h[maxc])
{
    dis[0]=0 ;
    for(int i=1;i<m;i++) dis[i]=dis[i-1]+h[i-1] ;
    int mi=INF ;
    for(int i=1;i<m;i++)
    {
        mi=min(mi, a[i-1]-dis[i-1]) ;
        a[i]=min(a[i],mi+dis[i]) ;
    }
    mi=INF ;
    for(int i=m-2;i>=0;i--)
    {
        mi=min(mi,a[i+1]+dis[i+1]) ;
        a[i]=min(a[i],mi-dis[i]) ;
    }
}
 
int H[maxn][maxc] , V[maxn][maxc] ;
 
void cal(int l,int r,int a[maxc][maxc])
{
    for(int i=0;i<m;i++) for(int j=l;j<=r;j++)
    {
        for(int k=0;k<m;k++)
            a[i][k]= j==l ? (i==k?0:INF) : (a[i][k]+V[j-1][k]) ;
        sweep_hor(a[i],H[j]) ;
    }
}
 
int K[maxc][maxc] ;
void merge(int a[maxc][maxc],int b[maxc][maxc],int c[maxc][maxc])
{
    for(int i=0;i<m;i++) for(int j=0;j<m;j++)
        c[i][j]=INF ;
    for(int i=0;i<m;i++) for(int j=0;j<m;j++)
        if(a[i][j]+b[j][i]<c[i][i])
            c[i][i]=a[i][j]+b[j][i] , K[i][i]=j ;
    for(int i=m-2;i>=0;i--) for(int j=i+1;j<m;j++)
        for(int k=K[i][j-1];k<=K[i+1][j];k++)
        if(a[i][k]+b[k][j]<c[i][j])
            c[i][j]=a[i][k]+b[k][j] , K[i][j]=k ;
    for(int i=1;i<m;i++) for(int j=i-1;j>=0;j--)
        for(int k=K[i-1][j];k<=K[i][j+1];k++)
        if(a[i][k]+b[k][j]<c[i][j])
            c[i][j]=a[i][k]+b[k][j] , K[i][j]=k ;
}
 
void build(int l,int r,int id)
{
    if(r-l<KK)
    {
        cal(l,r,ST[id]) ;
        return ;
    }
    int mid=(l+r)/2 ;
    build(l,mid,2*id) ;
    build(mid,r,2*id+1) ;
    merge(ST[2*id],ST[2*id+1],ST[id]) ;
}
 
void modify(int L,int R,int id,int pos)
{
    if(R-L<KK)
    {
        cal(L,R,ST[id]) ;
        return ;
    }
    int mid=(L+R)/2 ;
    if(pos<=mid) modify(L,mid,2*id,pos) ;
    else modify(mid,R,2*id+1,pos) ;
    merge(ST[2*id],ST[2*id+1],ST[id]) ;
}
 
void modify_hor(int x,int y,int val)
{
    H[x][y]=val ;
    modify(0,n-1,1,x) ;
    if(x<n-1) modify(0,n-1,1,x+1) ;
}
 
void modify_ver(int x,int y,int val)
{
    V[x][y]=val ;
    modify(0,n-1,1,x+1) ;
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m-1;j++) scanf("%d",&H[i][j]) ;
    for(int i=0;i<n-1;i++) for(int j=0;j<m;j++) scanf("%d",&V[i][j]) ;
    build(0,n-1,1) ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int op ; scanf("%d",&op) ;
        if(op==1)
        {
            int x,y,val ; scanf("%d%d%d",&x,&y,&val) ;
            modify_hor(x,y,val) ;
        }
        else if(op==2)
        {
            int x,y,val ; scanf("%d%d%d",&x,&y,&val) ;
            modify_ver(x,y,val) ;
        }
        else
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            printf("%d\n",ST[1][x][y]) ;
        }
    }
}