Hellc

「题目描述」

给定一个 $2$ 行 $N$ 列的网格图，每次询问一个区间内所有点的最小生成树，要求支持修改边权。

共 $M$ 次操作，$ 1 \leq N, M \leq 60000 $

「题目链接」

BZOJ 3995 道路修建 「SDOI 2015」

「解题思路」

做过 BZOJ 1018 堵塞的交通 的话，应该能容易想到用线段树维护区间上的信息。

假设某线段树节点维护区间 $[l, r]$ ，区间中点 $m$ ，那么左儿子维护 $[l, m]$ ，右儿子维护 $[m + 1, r]$ 。

考虑一个区间中的点（两排），将四个角上的点称之为顶点，其他的称之为内部的点。

能和外界联通的点只有顶点，所以为了合并后整体联通，必须保证 内部的点和至少一个顶点联通 。

保证这一点后，对每个区间就只需考虑四个顶点了。

考虑进行信息合并，能把两边连起来的，只有从 $m$ 到 $m + 1$ 的两条边，涉及左儿子的右上、右下，右儿子的左上、左下四个顶点。

那么我们主要考虑的，将是从 $m$ 到 $m + 1$ 的两条边，左儿子的右上、右下，右儿子的左上、左下四个顶点。

这个时候我们就会发现，这两条边是不能随便连的，因为我们不知道这四个顶点间的连通性。

不合适的连边，会导致内部的点不和顶点联通，或者形成环。

这就启示我们，需要把顶点间的连通性加入信息的状态。

每个线段树节点维护 $f(a, b)$ ，表示左上角和左下角连通性为 $a$ ，右上角和右下角连通性为 $b$ 时的最优答案。连通性为 $1$ 代表联通，为 $0$ 代表不联通。

然后合并的时候根据四个端点的联通性，选择连一条边，或者都连上，计算即可。

在这里给出核心代码：

Info merge(const Info &l, const Info &r, int lenU, int lenD){
    // l 代表左儿子信息，r 代表右儿子信息, lenU 代表 m 到 m + 1 的上边那条边，lenD 代表下边那条
    Info i;

    int lenMin = std::min(lenU, lenD), lenSum = lenU + lenD;
    // lenMin 是连一条边的代价，lenSum 是都连上的代价。
    for(int a = 0; a <= 1; a++){
        for(int b = 0; b <= 1; b++){
            i[a][b] = std::min(
                lenMin + l[a][1] + r[1][b], // 各自联通，只能连一条边，否则会形成环
                lenSum + std::min(l[a][0] + r[1][b], l[a][1] + r[0][b]) // 至少一对点不联通，必须连两条边
            );
        }
    }

    return i;
}

总结：主要问题在于信息的状态表示，在转移或者合并不了，或者无法保证合法时，可以考虑更改状态表示。

「AC 代码」

#include <cstdio>
#include <algorithm>

struct Info{
    int f[2][2];

    int* operator[](int i){
        return f[i];
    }

    const int* operator[](int i) const{
        return f[i];
    }

    Info(int a = 0, int b = 0, int c = 0, int d = 0){
        f[0][0] = a, f[0][1] = b, f[1][0] = c, f[1][1] = d;
    }

    static Info merge(const Info &l, const Info &r, int lenU, int lenD){
        Info i;

        int lenMin = std::min(lenU, lenD), lenSum = lenU + lenD;
        for(int a = 0; a <= 1; a++){
            for(int b = 0; b <= 1; b++){
                i[a][b] = std::min(lenMin + l[a][1] + r[1][b], lenSum + std::min(l[a][0] + r[1][b], l[a][1] + r[0][b]));
            }
        }

        return i;
    }
};

const int MAX_N = 60000;

int lenU[MAX_N], lenD[MAX_N], lenV[MAX_N + 1];

inline Info calc(int x){
    return Info(0, 0, 0, lenV[x]);
}

struct Node{
#define mid ((this->l + this->r) >> 1)
    int l, r;
    Node *lc, *rc;
    Info i;

    Node(int l = 0, int r = 0) : l(l), r(r), lc(NULL), rc(NULL) {}

    void update(){
        i = Info::merge(lc->i, rc->i, lenU[mid], lenD[mid]);
    }

    void build(){
        if(r - l == 1){
            i = calc(l);
        } else{
            (lc = new Node(l, mid))->build(), (rc = new Node(mid, r))->build();
            update();
        }
    }

    void refresh(int x){
        if(r - l == 1){
            i = calc(l);
        } else{
            if(x < mid) lc->refresh(x); else rc->refresh(x);
            update();
        }
    }

    Info query(int l, int r){
        if(l == this->l && this->r == r) return i;
        else{
            if(r <= mid) return lc->query(l, r); else if(l >= mid) return rc->query(l, r);
            else return Info::merge(lc->query(l, mid), rc->query(mid, r), lenU[mid], lenD[mid]);
        }
    }
#undef mid
} *gm;

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++) scanf("%d", &lenU[i]);
    for(int i = 1; i < n; i++) scanf("%d", &lenD[i]);
    for(int i = 0; i < n; i++) scanf("%d", &lenV[i]);

    (gm = new Node(0, n))->build();

    for(int i = 1; i <= m; i++){
        char cmd;
        do cmd = getchar(); while(cmd != 'C' && cmd != 'Q');

        if(cmd == 'Q'){
            int l, r;
            scanf("%d%d", &l, &r), l--, r--;
            printf("%d\n", gm->query(l, r + 1)[1][1]);
        } else if(cmd == 'C'){
            int x0, y0, x1, y1, val;
            scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &val), y0--, y1--;

            if(x0 > x1 || (x0 == x1 && y0 > y1)) std::swap(x0, x1), std::swap(y0, y1);
            
            if(x1 - x0 == 1){
                lenV[y0] = val;
            } else if(y1 - y0 == 1){
                if(x0 == 1) lenU[y0 + 1] = val;
                else if(x0 == 2) lenD[y0 + 1] = val;
            }

            gm->refresh(y0);
        } else{
            throw;
        }
    }

    return 0;
}