题解：P5618 [SDOI2015] 道路修建

· · 题解

记第 i 列上下两行与 i-1 列连边的权值分别为 a_i,b_i，第 i 列上下相连的权值为 w_i。

考虑 DP，设 f_{i,0/1} 表示考虑完前 i 列，第 i 列上下是否连通的最小花费。

转移：

f_{i,0}=\min(f_{i-1,0}+a_i+b_i,f_{i-1,1}+\min(a_i,b_i))\\ f_{i,1}=\min(f_{i-1,0}+a_i+b_i+w_i,f_{i-1,1}+a_i+b_i+w_i-\max(a_i,b_i,w_i))

使用 \min+ 的广义矩阵乘法刻画转移，这种矩阵乘法仍然具有结合律。

具体地：

\begin{bmatrix} f_{i-1,0}&f_{i-1,1} \end{bmatrix} \begin{bmatrix} a_i+b_i&a_i+b_i+w_i\\ \min(a_i,b_i)&a_i+b_i+w_i-\max(a_i,b_i,w_i) \end{bmatrix} = \begin{bmatrix} f_{i,0}&f_{i,1} \end{bmatrix}

用线段树维护一个区间的转移矩阵相乘的结果，可以支持单点修改。

#include<bits/stdc++.h>
#define N 60005
using namespace std;
int n,m,a[N],b[N],w[N];
constexpr int inf=0x3f3f3f3f;
struct Mat{
    int a[2][2];
    Mat operator*(const Mat &x){
        Mat res;for(int i:{0,1}) for(int j:{0,1}){
            res.a[i][j]=inf;for(int k:{0,1})
                res.a[i][j]=min(res.a[i][j],a[i][k]+x.a[k][j]);
        }return res;
    }
};
class SGT{
    #define l(i) ((i)<<1)
    #define r(i) ((i)<<1|1)
    private:Mat tr[N<<2];
    public:
        void upd(int p,int x=1,int l=2,int r=n){
            if(l==r){
                tr[x].a[0][1]=tr[x].a[1][1]=a[p]+b[p]+w[p];
                tr[x].a[0][0]=a[p]+b[p],tr[x].a[1][0]=min(a[p],b[p]);
                tr[x].a[1][1]-=max({a[p],b[p],w[p]});return;
            }
            int mid=l+r>>1;p<=mid?
            upd(p,l(x),l,mid):
            upd(p,r(x),mid+1,r);
            tr[x]=tr[l(x)]*tr[r(x)];
        }
        Mat query(int ql,int qr,int x=1,int l=2,int r=n){
            if(ql<=l&&qr>=r) return tr[x];int mid=l+r>>1;
            if(ql<=mid&&qr<=mid) return query(ql,qr,l(x),l,mid);
            if(ql>mid&&qr>mid) return query(ql,qr,r(x),mid+1,r);
            return query(ql,qr,l(x),l,mid)*query(ql,qr,r(x),mid+1,r);
        }
}T;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++) scanf("%d",a+i);
    for(int i=2;i<=n;i++) scanf("%d",b+i);
    for(int i=1;i<=n;i++) scanf("%d",w+i),i^1?T.upd(i):void();
    for(int i=1;i<=m;i++){
        char op=getchar();
        for(;op^'C'&&op^'Q';op=getchar());
        if(op=='C'){
            int x,y,p,q,v;
            scanf("%d%d%d%d%d",&x,&y,&p,&q,&v);
            if(y^q) y=max(y,q),(x^2?a[y]:b[y])=v;
            else w[y]=v;if(y^1) T.upd(y);
        }
        else{
            Mat A;int l,r;scanf("%d%d",&l,&r);
            A.a[0][0]=0,A.a[0][1]=w[l],A.a[1][0]=A.a[1][1]=inf;
            if(l^r) A=A*T.query(l+1,r);printf("%d\n",A.a[0][1]);
        }
    }
    return 0;
}