#4740. 「KTSC 2019 R1」产油国 题解

题目理解

这是一个图论优化问题：给定一条主线（$N$ 个节点排成链，有 $N-1$ 条旧路）和 $M$ 条新建的边，要选择两条边设置收费站，使得所有车辆（每对节点间有车辆）支付的过路费总和最大。

关键点：

• 每辆车走最短路径（按收费站数量）
• 每条边收费 $1$，经过两个收费边收 $2$
• 总收益 = 所有路径的收费总和

核心算法

算法标签：图论 区间覆盖 线段树 贪心 组合计数

1. 问题转化

设选择的两条边为 $e_1$ 和 $e_2$，总收益为：

• 经过 $e_1$ 的路径数 + 经过 $e_2$ 的路径数 + 2 × 同时经过两条边的路径数

由于车辆数量固定，最大化收益等价于最大化经过收费边的路径数量。

2. 算法框架

步骤1：处理新建边的影响

// 使用差分数组统计每个旧边被新建边"覆盖"的次数
for (int i = 0; i < m; i++) {
    c[A[i]]++;
    c[B[i]]--;
}
for (int i = 1; i < n; i++) {
    c[i] += c[i - 1];
    // 如果c[i] == 0，说明边(i,i+1)没有被任何新建边替代
    if (!c[i]) 
        pq.push(1LL * i * (n - i));  // 这条边的路径通过数
}

算法标签：差分数组 区间计数

步骤2：贪心选择未被覆盖的边

// 选择通过数最大的两条未被覆盖的边
if (!pq.empty()) {
    res += pq.top(); pq.pop();
}
if (!pq.empty()) {
    res += pq.top(); pq.pop();
}

算法标签：贪心算法 优先队列

步骤3：考虑单条被覆盖边的情况

for (int i = 1; i < n; i++)
    if (c[i] == 1)  // 只被一条新建边覆盖
        res = max(res, 1LL * i * (n - i));

步骤4：线段树处理区间边界

// 计算每个位置i的右边界u[i]
S.i();
for (int i = 1; i <= m; i++)
    S.u(s[i], e[i], e[i] + 1);  // 区间最小值更新
for (int i = 1; i < n; i++)
    u[i] = min(n, S.g(i));  // 获取最小值

// 类似计算左边界l[i]

算法标签：线段树 区间最值 边界计算

步骤5：寻找最优边对

T.i();  // 初始化线段树
for (int i = 1, x, y; i < n; i++) {
    // 在有效范围内寻找最优的配对边
    x = T.ub(i, i + (n + 1) / 2);
    y = T.lb(i, i + n / 2);
    // ... 计算x,y的贡献
    res = max(res, 1LL * x * (n - x));
}

关键数据结构

线段树 Sg1

用于区间最小值更新和查询，计算每个边的有效边界。

线段树 Sg2

支持：

• ub(c, x)：在x右侧找第一个值小于c的位置
• lb(c, x)：在x左侧找第一个值小于c的位置

用于快速找到最优的配对边。

算法正确性分析

为什么这样能最大化收益？

1. 路径计数公式：边$(i,i+1)$的通过数 = $i × (n-i)$
2. 新建边影响：新建边提供了替代路径，减少某些旧边的通过数
3. 最优配对：选择距离适中的两条边，最大化同时经过两条边的路径数

关键观察

• 主线是链结构，路径唯一（除非有新建边）
• 两条边将链分成三段，同时经过两条边的路径必须跨越所有三段
• 最优解往往选择将链分成接近三等分的两条边

复杂度分析

• 预处理：$O(N + M \log N)$
• 线段树操作：$O(\log N)$ 每次
• 总复杂度：$O(N \log N)$，满足 $N \leq 5\times 10^5$ 的要求

算法标签总结

主要标签

• 图论 - 问题领域
• 线段树 - 核心数据结构
• 贪心算法 - 优化策略

技术标签

• 区间操作 - 处理新建边的影响
• 差分数组 - 高效统计覆盖次数
• 路径计数 - 组合数学计算

优化标签

• $O(N \log N)$算法 - 高效复杂度
• 预处理 - 离线计算加速
• 边界计算 - 确定有效范围

数据结构标签

• 优先队列 - 维护最大值
• 区间树 - 快速范围查询
• 最小值维护 - 线段树功能

关键创新点

1. 差分统计：高效处理新建边的覆盖影响
2. 边界计算：确定每条边的有效作用范围
3. 对称性利用：利用链结构的对称性寻找最优配对
4. 多情况考虑：分别处理未被覆盖、单覆盖、双覆盖的情况

样例验证

对于样例3（$N=4, M=0$）：

• 所有旧边都没有被覆盖
• 边通过数：$1×3=3$, $2×2=4$, $3×1=3$
• 最优选择：通过数4和3的两条边
• 总收益：$(4+3)×2=14$

这个解法通过巧妙的组合计数和高效的数据结构，解决了复杂的图论优化问题。