题目分析

有 $N$ 个车站排成一行，$M$ 条火车线路，每条线路 $i$ 从 $A_i$ 到 $B_i$，中间每站停车。
乘客可以在起点前后 $K-1$ 站内上车，在任意中间站或终点下车。
求从 $S$ 到 $T$ 的最少乘车次数。

---

核心思路

1. 问题转化

将问题转化为区间扩张问题：

• 定义 $[L, R]$ 表示当前能到达的车站范围
• 初始 $[L, R] = [S, S]$
• 每次乘车可以扩展这个区间
• 目标：让 $T \in [L, R]$

2. 单次乘车扩展

对于位置 $i$，考虑所有经过 $i$ 附近 $K$ 站的线路：

• 向右扩展：从 $i$ 出发，能到达的最左位置是所有以 $i$ 为起点附近上车的线路的最小终点
• 向左扩展：从 $i$ 出发，能到达的最右位置是所有以 $i$ 为起点附近上车的线路的最大终点

3. 倍增优化

使用倍增法预处理：

• $L[k][i]$：从 $i$ 出发，乘坐 $2^k$ 次车能到达的最左位置
• $R[k][i]$：从 $i$ 出发，乘坐 $2^k$ 次车能到达的最右位置

转移：

$$L[k][i] = \min_{j=L[k-1][i]}^{R[k-1][i]} L[k-1][j] $$$$R[k][i] = \max_{j=L[k-1][i]}^{R[k-1][i]} R[k-1][j] $$

---

算法实现

数据结构设计

Sgt1：线路信息管理

struct Sgt1 {
    multiset<int> s[N];  // 每个站点的所有线路终点
    int mn[4 * N], mx[4 * N];  // 线段树维护区间最小/最大终点
    
    // 添加线路：将终点加入对应站点的multiset
    void update(int u, int l, int r, int x, int val);
    
    // 查询区间最小终点
    int queryMin(int u, int l, int r, int x, int y);
    
    // 查询区间最大终点  
    int queryMax(int u, int l, int r, int x, int y);
};

Sgt2：倍增区间查询

struct Sgt2 {
    int mn[4 * N], mx[4 * N];  // 线段树维护L[k][i]或R[k][i]
    
    // 更新单点值
    void updateMin(int u, int l, int r, int x, int val);
    void updateMax(int u, int l, int r, int x, int val);
    
    // 查询区间最值
    int queryMin(int u, int l, int r, int x, int y);
    int queryMax(int u, int l, int r, int x, int y);
} sgt2[18];  // 18层倍增

---

代码流程

1. 初始化

cin >> n >> lim >> m;
sgt1.build(1, 1, n);

for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i];
    sgt1.update(1, 1, n, a[i], b[i]);  // 记录线路信息
}

2. 预处理第0层

for (int i = 1; i <= n; i++) {
    // 向右：从i出发，在[i, i+lim-1]上车能到的最左位置
    L[0][i] = sgt1.queryMin(1, 1, n, i, min(i + lim - 1, n));
    
    // 向左：从i出发，在[i-lim+1, i]上车能到的最右位置  
    R[0][i] = sgt1.queryMax(1, 1, n, max(i - lim + 1, 1), i);
    
    // 存入线段树供下一层使用
    sgt2[0].updateMin(1, 1, n, i, L[0][i]);
    sgt2[0].updateMax(1, 1, n, i, R[0][i]);
}

3. 倍增预处理

for (int i = 1; i <= 17; i++) {
    for (int j = 1; j <= n; j++) {
        // 关键：在上一层的可达区间内查询最值
        L[i][j] = sgt2[i-1].queryMin(1, 1, n, L[i-1][j], R[i-1][j]);
        R[i][j] = sgt2[i-1].queryMax(1, 1, n, L[i-1][j], R[i-1][j]);
        
        sgt2[i].updateMin(1, 1, n, j, L[i][j]);
        sgt2[i].updateMax(1, 1, n, j, R[i][j]);
    }
}

4. 查询处理

for (int i = 1, s, t; i <= q; i++) {
    cin >> s >> t;
    int l = s, r = s, ans = 0;
    
    // 从高位到低位尝试
    for (int j = 17; j >= 0; j--) {
        int nl = sgt2[j].queryMin(1, 1, n, l, r);
        int nr = sgt2[j].queryMax(1, 1, n, l, r);
        
        if (nl <= t && t <= nr) {
            continue;  // 已经能到达，不选择这层
        }
        
        l = nl;
        r = nr;
        ans += 1 << j;  // 选择这层
    }
    
    cout << (ans > n ? -1 : ans + 1) << '\n';
}

---

复杂度分析

• 预处理：$O(N \log N \log K)$
  • 17层倍增 × $N$个站点 × 线段树查询 $O(\log N)$
• 查询：$O(Q \log K)$
  • 每个查询17次 × 线段树查询 $O(\log N)$
• 空间：$O(N \log N)$

---

算法标签

主要算法：

• 倍增法
• 线段树
• 区间最值查询

相关技巧：

• 优化建图
• 二分答案思想
• 动态规划

---

总结

本题通过倍增+线段树巧妙地将复杂的乘车规划问题转化为区间扩展问题，利用线段树快速查询区间最值，倍增法快速逼近答案，实现了高效求解。