「ROI 2024 Day2」保持通信 题解

问题分析

我们有一个包含 $n$ 个城市的直线道路，每个城市 $i$ 有一个功率为 $a_i$ 的天线，覆盖区间为 $[\max(1, i-a_i), \min(n, i+a_i)]$。

卡车从 $s$ 到 $t$ ($s < t$) 的移动过程中，连接天线的规则是贪心的：

• 在起点 $s$ 选择覆盖 $s$ 且右端点 $R_i$ 最大的天线
• 当从 $v$ 移动到 $v+1$ 时，如果当前天线覆盖 $v+1$ 则保持，否则重新选择

定义 $f(s,t)$ 为重新连接次数，$F = \sum_{s=1}^{n-1} \sum_{t=s+1}^n f(s,t)$。

我们可以用功率为 $x$ 的备用天线替换任意一个现有天线，目标是最小化 $F$。

关键思路

1. 跳跃模型

将问题转化为跳跃模型：从位置 $p$ 出发，可以跳到 $g(p) = \max\{R_i \mid L_i \leq p \leq R_i\}$，即覆盖 $p$ 的所有天线中最大的右端点。

那么 $f(s,t)$ 就是从 $s$ 出发，不断跳到 $g(p)+1$，直到超过 $t$ 的跳跃次数减 1。

2. 高效计算总代价

直接计算所有 $(s,t)$ 对的 $f(s,t)$ 不可行。代码采用巧妙的预处理和贡献统计方法：

for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    int l = std::max(i - a[i], 1), r = std::min(i + a[i], n);
    R[l] = std::max(R[l], r + 1);  // 记录每个起点能跳到的最远位置+1
}

这里 R[l] 表示从位置 $l$ 出发，使用覆盖 $l$ 的天线能够到达的最远位置加 1。

3. 预处理跳跃信息

for (int i = 1; i <= n; i++) {
    R[i] = std::max(R[i], R[i - 1]);  // 前缀最大值，确保单调性
}

这步保证 R[i] 是单调不减的，即从位置 $i$ 出发至少能跳到 R[i]。

4. 计算初始总代价

for (int i = n; i >= 1; i--) {
    f[i] = f[R[i]] + n - R[i] + 1;  // 从i出发的所有路径的跳跃总次数
    siz[i] = 1;  // 初始化子树大小
}

这里 f[i] 表示从位置 $i$ 出发的所有 $(i,t)$ 路径的 $f(i,t)$ 之和。

5. 计算子树大小

for (int i = 1; i <= n; i++) {
    siz[R[i]] += siz[i];  // 统计每个位置作为起点的路径数量
}

siz[i] 表示以 $i$ 为起点的路径数量。

6. 重新计算 f 数组

for (int i = n; i >= 1; i--) {
    f[i] = f[R[i]] + n - i + 1;  // 另一种计算方式，用于后续优化
}

7. 前缀和数组

for (int i = 1; i <= n; i++) {
    s1[i] = s1[i - 1] + siz[i];           // siz 前缀和
    s2[i] = s2[i - 1] - 1LL * siz[i] * f[R[i]];  // 加权前缀和
    s3[i] = s3[i - 1] - 1LL * siz[i] * (n - R[i] + 1);  // 另一加权前缀和
}

这些前缀和数组用于快速计算替换天线后的代价变化。

8. 寻找最优替换

for (int i = 1; i <= n; i++) {
    int l = std::max(1, i - x), r = std::min(i + x, n) + 1;
    
    if (R[l] >= r || a[i] >= x)  // 如果替换没有改进，跳过
        continue;
    
    // 二分查找关键位置 p 和 q
    int sl = l, sr = r - 1, p = l;
    while (sl <= sr) {
        int mid = sl + sr >> 1;
        if (R[mid] < r) {
            p = mid, sl = mid + 1;
        } else {
            sr = mid - 1;
        }
    }
    
    // 继续二分查找 q
    sl = l, sr = p;
    int q = p;
    while (sl <= sr) {
        int mid = sl + sr >> 1;
        if (R[mid] > p) {
            sr = mid - 1, q = mid;
        } else {
            sl = mid + 1;
        }
    }
    
    // 计算替换后的代价减少量
    delta = std::min(delta, s3[q - 1] - s3[l - 1] + s2[p] - s2[q - 1] + 
                      (s1[p] - s1[q - 1]) * f[r]);
}

算法复杂度

• 时间复杂度：$O(n \log n)$，主要来自二分查找
• 空间复杂度：$O(n)$

总结

该解法通过巧妙的预处理和数据结构，将原本需要 $O(n^2)$ 时间的问题优化到 $O(n \log n)$。核心思想是将路径跳跃问题转化为区间覆盖问题，利用单调性和前缀和快速计算代价变化。

代码通过维护多个数组来跟踪跳跃信息、子树大小和前缀和，使得在评估每个可能的替换时能够快速计算出其对总代价的影响。