题目理解

有 $n$ 个火车站排成一条直线，$m$ 条火车轨道覆盖不同的区间。火车从起点 $x$ 出发，只能单向行驶，但在被多条轨道覆盖的车站可以切换轨道。求所有可能到达的终点车站（即轨道的端点）。

关键点：

• 火车只能停在某条轨道的端点
• 行驶方向一旦确定就不能改变
• 轨道重叠处可以切换轨道

核心思路

关键观察

1. 连续覆盖区间：从起点出发，向左右两个方向扩展，火车只能在连续被轨道覆盖的区间内行驶
2. 端点特性：停车站必须是某个轨道的端点
3. 方向限制：
   • 向左行驶时，只能到达左端点
   • 向右行驶时，只能到达右端点

算法设计

使用差分数组+贪心扩展的方法：

1. 统计覆盖情况：用差分数组记录每个车站被多少条轨道覆盖
2. 标记端点：记录哪些车站是轨道的左端点或右端点
3. 扩展边界：从起点向左右扩展，找到最大的连续覆盖区间
4. 收集答案：在扩展区间内，起点左侧收集左端点，起点右侧收集右端点

算法步骤

步骤详解

1. 初始化数组

   • D[i]：差分数组，用于计算每个车站的覆盖次数
   • lp[i]：标记车站 $i$ 是否是某个轨道的左端点
   • rp[i]：标记车站 $i$ 是否是某个轨道的右端点

2. 处理输入数据

   • 对于每个轨道 $[l, r]$：
     • D[l]++, D[r+1]--（差分标记）
     • lp[l] = 1, rp[r] = 1（标记端点）

3. 计算前缀和

   • 通过前缀和将差分数组转换为实际的覆盖次数数组

4. 扩展边界

   • 从起点 $k$ 向左找到第一个不被覆盖的车站 l
   • 从起点 $k$ 向右找到第一个不被覆盖的车站 r
   • 连续覆盖区间为 $[l+1, r-1]$

5. 输出答案

   • 在 $[l+1, k)$ 区间内输出所有左端点
   • 在 $(k, r-1]$ 区间内输出所有右端点

复杂度分析

• 时间复杂度：$O(n + m)$

  • 处理 $m$ 条轨道：$O(m)$
  • 前缀和计算：$O(n)$
  • 边界扩展：$O(n)$
  • 答案收集：$O(n)$

• 空间复杂度：$O(n)$

  • 使用三个长度 $n+2$ 的数组

代码实现与解析

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    
    // 数组定义
    vector<int> D(n + 2), lp(n + 2), rp(n + 2);
    // D: 差分数组，用于计算每个车站被多少轨道覆盖
    // lp: 标记左端点，rp: 标记右端点

    // 处理每条轨道
    for (int i = 0, l, r; i < m && cin >> l >> r; i++) {
        D[l]++; D[r + 1]--;    // 差分标记，表示[l,r]区间覆盖次数+1
        lp[l] = 1;             // 标记l为左端点
        rp[r] = 1;             // 标记r为右端点
    }

    // 计算前缀和，得到每个车站的实际覆盖次数
    for (int i = 1; i <= n; i++) {
        D[i] += D[i - 1];
    }

    // 扩展边界：找到从起点k出发的连续覆盖区间
    int l = k, r = k;
    while (l && D[l]) l--;      // 向左扩展，找到第一个不被覆盖的车站
    while (r <= n && D[r]) r++; // 向右扩展，找到第一个不被覆盖的车站
    // 此时连续覆盖区间为 [l+1, r-1]

    // 收集并输出答案
    for (int i = l + 1; i <= r - 1; i++) {
        // 起点左侧：只能到达左端点（向左行驶）
        // 起点右侧：只能到达右端点（向右行驶）
        if ((i < k && lp[i]) || (i > k && rp[i])) {
            cout << i << " ";
        }
    }
    
    return 0;
}

样例验证

样例1

输入：
7 5 4
3 4
4 6
1 3
5 7
4 6

处理过程：
- 覆盖区间：[1,3], [3,4], [4,6], [4,6], [5,7]
- 连续覆盖区间：[1,7]
- 左端点：1,3,4,5；右端点：3,4,6,7
- 起点4左侧的左端点：1,3
- 起点4右侧的右端点：6,7
输出：1 3 6 7

算法正确性证明

1. 完备性：算法考虑了所有可能的行驶方向和轨道切换情况
2. 正确性：只有轨道的端点才能作为停车站，且必须满足方向约束
3. 高效性：线性复杂度处理大规模数据

该解法巧妙利用了差分数组和贪心扩展，避免了复杂的图遍历，以简洁高效的方式解决了问题。