「SDOI2015」道路修建 题解

题目大意

给定一个 $2$ 行 $N$ 列的网格图，有三种边：

• 第一行相邻列之间的边（横向边）
• 第二行相邻列之间的边（横向边）
• 同一列两行之间的边（纵向边）

支持两种操作：

1. 修改某条边的权值
2. 查询区间 $[L,R]$ 列的最小生成树大小

问题分析

这是一个经典的区间最小生成树问题，需要维护一个 $2 \times (R-L+1)$ 个点的网格图在区间 $[L,R]$ 上的最小生成树权值。

关键观察

对于 $2 \times k$ 的网格图，最小生成树具有特殊的结构性质：

• 总点数：$2k$
• 最小生成树边数：$2k-1$
• 每列至少有一条纵向边被选中（否则上下两行不连通）
• 实际上每列恰好有一条纵向边被选中（如果某列有两条，可以删除一条并连接横向边）

数据结构设计

使用线段树维护区间信息。每个节点 $[l,r]$ 存储：

• $val$：区间 $[l,r]$ 的最小生成树权值
• $lu, ld$：左右边界的连通性信息
• 其他辅助信息来合并左右子树

具体来说，每个线段树节点存储：

• 左边界第一行和第二行的连通性
• 右边界第一行和第二行的连通性
• 最小生成树权值
• 边界列的纵向边选择情况

合并操作

当合并两个相邻区间 $[l,mid]$ 和 $[mid+1,r]$ 时，需要考虑中间列 $(mid, mid+1)$ 之间的两条横向边的连接情况。

合并时有多种情况（$2^2 = 4$ 种），需要枚举中间两条横向边的选择情况，计算最小生成树。

时间复杂度

• 每次合并：$O(1)$（常数时间枚举所有情况）
• 线段树单次操作：$O(\log N)$
• 总复杂度：$O((N+M)\log N)$

代码框架

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 60005;

struct Node {
    // 存储区间最小生成树信息
    long long val;
    int lu, ld, ru, rd; // 边界连通性
    // 其他辅助信息...
};

int n, m;
int A[MAXN], B[MAXN], C[MAXN]; // 第一行横向、第二行横向、纵向边权值

struct SegmentTree {
    Node tree[MAXN * 4];
    
    Node merge(Node L, Node R, int mid) {
        // 合并两个相邻区间的信息
        Node res;
        // 枚举中间两条横向边的选择情况
        // 计算最小生成树权值和连通性
        return res;
    }
    
    void build(int node, int l, int r) {
        if (l == r) {
            // 初始化叶子节点（单列）
            return;
        }
        int mid = (l + r) / 2;
        build(node*2, l, mid);
        build(node*2+1, mid+1, r);
        tree[node] = merge(tree[node*2], tree[node*2+1], mid);
    }
    
    void update(int node, int l, int r, int pos, int type) {
        // 根据边的类型更新
        if (l == r) {
            // 更新叶子节点
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(node*2, l, mid, pos, type);
        else update(node*2+1, mid+1, r, pos, type);
        tree[node] = merge(tree[node*2], tree[node*2+1], mid);
    }
    
    Node query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        if (qr <= mid) return query(node*2, l, mid, ql, qr);
        if (ql > mid) return query(node*2+1, mid+1, r, ql, qr);
        Node L = query(node*2, l, mid, ql, qr);
        Node R = query(node*2+1, mid+1, r, ql, qr);
        return merge(L, R, mid);
    }
};

SegmentTree seg;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) scanf("%d", &A[i]);
    for (int i = 1; i < n; i++) scanf("%d", &B[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &C[i]);
    
    seg.build(1, 1, n);
    
    while (m--) {
        char op[2];
        scanf("%s", op);
        if (op[0] == 'Q') {
            int l, r;
            scanf("%d%d", &l, &r);
            Node res = seg.query(1, 1, n, l, r);
            printf("%lld\n", res.val);
        } else {
            int x0, y0, x1, y1, w;
            scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &w);
            // 更新对应的边权值
            // 调用 seg.update
        }
    }
    
    return 0;
}

总结

本题是区间最小生成树的经典问题，主要难点在于：

1. 设计合适的数据结构维护区间连通信息
2. 高效合并相邻区间的信息
3. 处理动态修改操作

使用线段树维护区间最小生成树信息，通过精心设计的状态表示和合并操作，可以在对数时间内完成查询和修改。