题解

就是线段树维护一下转移矩阵

分成两种情况，一种是前面有两个联通块，一种是前面有一个联通块

从一个联通块转移到一个联通块

也就是新加一列的三个边选其中两条即可

从一个联通块转移到两个联通块

不连竖着的那条边，横着的两条边转移一条短的即可

从两个联通块转移到一个联通块

新加的一列三个边全连上

从两个联通块转移到两个联通块

连上横着的两条边

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define pdi pair
      
       #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define eps 1e-8#define mo 974711#define MAXN 60005//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
       
        void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
        
         void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}int64 a[2][MAXN],b[MAXN];int N,M;struct Matrix {    int64 f[2][2];    Matrix() {    for(int i = 0 ; i < 2 ; ++i) for(int j = 0 ; j < 2 ; ++j) f[i][j] = 1e10;    }    friend Matrix operator * (const Matrix &a,const Matrix &b) {    Matrix c;    for(int i = 0 ; i < 2 ; ++i) {        for(int j = 0 ; j < 2 ; ++j) {        for(int k = 0 ; k < 2 ; ++k) {            c.f[i][j] = min(c.f[i][j],a.f[i][k] + b.f[k][j]);        }        }    }    return c;    }};struct node {    int l,r;Matrix m;}tr[MAXN * 4];void update(int u) {    tr[u].m = tr[u << 1].m * tr[u << 1 | 1].m;}Matrix Calc(int c) {    Matrix res;    res.f[0][1] = min(a[0][c - 1],a[1][c - 1]);    res.f[0][0] = min(a[0][c - 1] + a[1][c - 1],b[c] + min(a[0][c - 1],a[1][c - 1]));    res.f[1][0] = a[0][c - 1] + a[1][c - 1] + b[c];    res.f[1][1] = a[0][c - 1] + a[1][c - 1];    return res;}void build(int u,int l,int r) {    tr[u].l = l;tr[u].r = r;    if(l == r) {    tr[u].m = Calc(l);    return;    }    int mid = (l + r) >> 1;    build(u << 1,l,mid);    build(u << 1 | 1,mid + 1,r);    update(u);}void Change(int u,int pos) {    if(tr[u].l == tr[u].r) {tr[u].m = Calc(pos);return;}    int mid = (tr[u].l + tr[u].r) >> 1;    if(pos <= mid) Change(u << 1,pos);    else Change(u << 1 | 1,pos);    update(u);}Matrix Query(int u,int l,int r) {    if(tr[u].l == l && tr[u].r == r) return tr[u].m;    int mid = (tr[u].l + tr[u].r) >> 1;    if(r <= mid) return Query(u << 1,l,r);    else if(l > mid) return Query(u << 1 | 1,l,r);    else return Query(u << 1,l,mid) * Query(u << 1 | 1,mid + 1,r);}void Init() {    read(N);read(M);    for(int i = 0 ; i <= 1 ; ++i) {    for(int j = 1 ; j < N ; ++j) {        read(a[i][j]);    }    }    for(int j = 1 ; j <= N ; ++j) {    read(b[j]);    }    build(1,1,N);}void Solve() {    char op[5];    int l,r;int x0,y0,x1,y1;    int64 w;    for(int i = 1 ; i <= M ; ++i) {    scanf("%s",op + 1);    if(op[1] == 'Q') {        read(l);read(r);        if(l == r) {out(b[l]);enter;}        else {        Matrix t = Query(1,l + 1,r);        out(min(t.f[1][0],b[l] + t.f[0][0]));enter;        }    }    else {        read(x0);read(y0);read(x1);read(y1);read(w);        if(x0 == x1) {        if(y0 > y1) swap(y0,y1);        a[x0 - 1][y0] = w;        Change(1,y1);        }        else {        b[y0] = w;        Change(1,y0);        }    }    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Init();    Solve();}