这是SDOI2019"世界地图"题目的代码，我来为你分析关键部分并提供详细题解。

题目核心思路

这是一个在环形网格图上处理最小生成树问题，需要高效处理多个查询。

关键数据结构

struct Gph {
    edge e[N * 4];  // 存储边的数组
    int len;        // 边数
    ll val;         // 生成树权值和
} pre[M], suf[M];   // 前缀和后缀信息

算法核心

1. 预处理前缀和后缀

   • pre[i]: 存储经度1到i区域的最小生成树信息
   • suf[i]: 存储经度i到m区域的最小生成树信息

2. 合并操作

   • 对于查询[l, r]，将pre[l-1]和suf[r+1]合并
   • 合并时考虑连接两部分的横向边（环形边）

关键函数分析

合并函数 merge:

Gph merge(Gph A, Gph B) {
    // 1. 清空临时变量
    cln();
    tmp.val = A.val + B.val;
    
    // 2. 合并边集
    for (rg i = 1; i <= A.len; ++i)
        e[++le] = A.e[i];
    
    // 3. 处理环形连接
    if (!tp) {
        for (rg i = 1; i <= B.len; ++i)
            e[++le] = B.e[i];
    } else {
        // 特殊处理环形边
        for (rg i = 1; i <= n; ++i)
            e[++le] = (edge){i, i + 4 * n, R[i][m]};
    }
    
    // 4. Kruskal算法求最小生成树
    sort(e + 1, e + le + 1);
    for (rg i = 1; i <= sum; ++i) F[i] = i;
    
    for (rg i = 1; i <= le; ++i)
        if (fd(e[i].x) ^ fd(e[i].y))
            ADD(e[i].x, e[i].y, e[i].w),
            F[F[e[i].x]] = F[e[i].y],
            tmp.val += e[i].w;
    
    return tmp;
}

DFS处理连通性:

bool dfs(ci x, ci f) {
    vis[x] = 1;
    int tmp = 0;
    for (rg i = head[x], y; i; i = nx[i])
        if ((y = to[i]) ^ f)
            tmp += dfs(y, x);
    
    // 标记关键节点
    if (tmp > 1 || x <= n || x > 4 * n)
        tmp = c[x] = 1;
    
    return tmp != 0;
}

完整题解

问题分析

• 网格大小：n×m（n≤100，m≤10000）
• 经度方向是环形的
• 每个查询指定战争国家范围[l, r]
• 需要为和平国家构建最小生成树

解决方案

1. 预处理阶段：

   • 生成横向边R和纵向边D的权重
   • 计算前缀pre[i]和后缀suf[i]的生成树信息

2. 查询处理：

   • 对于查询[l, r]，合并pre[l-1]和suf[r+1]
   • 添加必要的环形边连接两部分
   • 计算合并后的最小生成树

时间复杂度

• 预处理：O(nm log n)
• 每个查询：O(n log n)
• 总体复杂度可接受

关键优化

• 使用前缀后缀思想避免重复计算
• 只存储必要的边信息而非完整图
• 利用Kruskal算法的高效性

这个解法巧妙地将环形网格问题转化为线性处理，通过预处理大大加快了查询速度。