为了解决这个问题，我们需要为每个查询找到在和平国家之间构建最小生成树（MST）的最小安保代价。和平国家是指不在给定经度范围 [l, r] 内的国家。解决方案包括预处理网格的横向和纵向边的权重，然后利用前缀和后缀数组来高效计算每个查询的MST代价。

方法思路

1. 问题分析：该问题涉及一个由n行m列组成的网格，其中横向边形成环状结构。每个查询指定一个经度范围 [l, r]，表示处于战争状态的国家。目标是找到连接所有和平国家（不在 [l, r] 范围内的国家）的MST的最小代价。

2. 关键洞察：

   • 横向边：对于每一行，和平国家形成一个连续的段（由于网格的环状结构）。连接该段内所有国家的代价是该段内所有横向边的权重之和。
   • 纵向边：连接所有行所需的代价是每对相邻行之间最小纵向边权重的总和，这些纵向边必须位于和平国家所在的列。

3. 预处理：

   • 生成横向边（H）和纵向边（V）的权重使用给定的随机数生成器。
   • 对于每一行，计算横向边权重的前缀和（P）和后缀和（Q），以便快速计算任何连续段的和。
   • 对于纵向边，计算每对相邻行的前缀最小值（PV）和后缀最小值（SV），以便快速找到和平国家列中的最小权重。

4. 查询处理：对于每个查询 (l, r)：

   • 纵向代价是每对相邻行在和平国家列中的最小纵向边权重之和。
   • 横向代价是所有行在和平国家段内横向边权重之和。
   • 总代价是纵向和横向代价的总和。

解决代码

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

const int MAX_N = 101;
const int MAX_M = 10001;

unsigned int SA, SB, SC;
int lim;

int getweight() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC % lim + 1;
}

int n, m;
int H[MAX_N][MAX_M];
int V[MAX_N][MAX_M];
long long P[MAX_N][MAX_M];
long long Q[MAX_N][MAX_M];
int PV[MAX_N][MAX_M];
int SV[MAX_N][MAX_M];

int main() {
    cin >> n >> m >> SA >> SB >> SC >> lim;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int w = getweight();
            if (j < m) {
                H[i][j] = w;
            } else {
                H[i][j] = w;
            }
        }
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int w = getweight();
            V[i][j] = w;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        P[i][0] = 0;
        for (int j = 1; j <= m; j++) {
            P[i][j] = P[i][j-1] + H[i][j];
        }
        Q[i][m+1] = 0;
        for (int j = m; j >= 1; j--) {
            Q[i][j] = Q[i][j+1] + H[i][j];
        }
    }
    
    for (int i = 1; i < n; i++) {
        PV[i][0] = INT_MAX;
        for (int j = 1; j <= m; j++) {
            PV[i][j] = min(PV[i][j-1], V[i][j]);
        }
        SV[i][m+1] = INT_MAX;
        for (int j = m; j >= 1; j--) {
            SV[i][j] = min(SV[i][j+1], V[i][j]);
        }
    }
    
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        long long cost_vertical = 0;
        for (int i = 1; i < n; i++) {
            int a = PV[i][l-1];
            int b = SV[i][r+1];
            cost_vertical += min(a, b);
        }
        long long cost_horizontal = 0;
        for (int i = 1; i <= n; i++) {
            long long left_sum = 0;
            if (l - 2 >= 1) {
                left_sum = P[i][l-2];
            }
            long long right_sum = Q[i][r+1];
            cost_horizontal += left_sum + right_sum;
        }
        cout << cost_vertical + cost_horizontal << endl;
    }
    
    return 0;
}

样例中每条道路的安保代价

代码解释

1. 输入和初始化：读取网格的维度n和m，以及随机数生成器的参数SA、SB、SC和lim。使用生成器生成横向边（H）和纵向边（V）的权重。
2. 预处理：
   • 计算每行横向边权重的前缀和（P）和后缀和（Q），以便快速计算任意连续段的和。
   • 计算每对相邻行纵向边权重的前缀最小值（PV）和后缀最小值（SV），以便快速找到和平国家列中的最小权重。
3. 查询处理：对于每个查询 (l, r)：
   • 计算纵向代价，即每对相邻行在和平国家列中的最小纵向边权重之和。
   • 计算横向代价，即所有行在和平国家段内横向边权重之和。
   • 输出总代价，即纵向和横向代价的总和。

这种方法通过预处理实现了高效查询处理，适用于大规模输入。