题目理解

我们有一个长度为 $G$ 的线性机场，登机口按距离排序（第 $i$ 个登机口距离入口 $100i$ 米）。机场中有 $N$ 个单向自动扶梯，每个扶梯从 $A_i$ 到 $B_i$，速度为 $S_i$。人可以以速度 $W$ 步行，在扶梯上时速度为 $W + S_i$。

目标是回答 $Q$ 个询问：从登机口 $X_i$ 到 $Y_i$ 的最短时间。

问题分析

1. 移动方式

• 纯步行：速度为 $W$，时间与距离成正比
• 使用扶梯：在扶梯上速度为 $W + S_i$，但只能从起点坐到终点

2. 关键观察

• 机场是一维线性结构
• 扶梯有方向性：从左到右或从右到左
• 可以组合使用多个扶梯和步行段

算法思路

1. 离散化处理

由于 $G$ 可达 $10^9$，但实际使用的登机口只有 $O(N + Q)$ 个，首先进行离散化：

sort(mp + 1, mp + n + 1);
n = unique(mp + 1, mp + n + 1) - mp - 1;
for (i = 1; i <= Q; ++i)
    b[i].x = MP(b[i].x), b[i].y = MP(b[i].y);

2. 扶梯分类处理

将扶梯分为两个方向：

• 向右扶梯 $(x < y)$：存入 g 数组
• 向左扶梯 $(x > y)$：存入 h 数组

3. 区间填充与预处理

rec 函数处理扶梯区间：

• 对扶梯按起点排序
• 填充扶梯之间的空白区间（纯步行段）
• 计算每个区间的前缀和 w2

4. 动态规划计算最短时间

核心思想：对于每个区间，计算从左端点到区间内各点的最短时间（L 数组）和从区间内各点到右端点的最短时间（R 数组）。

状态定义

• G[x]：点 $x$ 所在的区间编号
• H[x]：点 $x$ 所在的向左扶梯区间编号
• L[x]：从区间左端点到 $x$ 的最短时间
• R[x]：从 $x$ 到区间右端点的最短时间

状态转移

从左向右计算 L 数组：

for (x = l + 1; x < r; ++x) {
    L[x] = L[x - 1] + W1(x - 1, x);  // 纯步行
    
    if (有向左扶梯可用) {
        v1 = 步行到扶梯终点 + 扶梯时间;
        L[x] = min(L[x], 通过扶梯的转移时间);
    }
}

从右向左计算 R 数组：

for (x = r - 1; x > l; --x) {
    R[x] = R[x + 1] + W1(x, x + 1);  // 纯步行
    
    if (有向左扶梯可用) {
        v1 = 步行到扶梯起点 + 扶梯时间;
        R[x] = min(R[x], 通过扶梯的转移时间);
    }
}

5. 查询处理

对于查询 $(x, y)$：

• 在同一区间内：min(直接步行, DR(x) + R[y])
• 在不同区间内：DR(x) + DL(y) + 中间区间步行时间

其中：

• DR(x)：从 $x$ 到所在区间右端的最短时间
• DL(y)：从 $y$ 所在区间左端到 $y$ 的最短时间

代码核心函数

离散化映射

#define MP(x) lower_bound(mp+1,mp+n+1,x)-mp

步行时间计算

ld W1(int l, int r) {
    return 100.*(mp[r] - mp[l]) / W;
}

区间端点最短时间

ld DR(int x) {
    return min(W1(x, g[G[x]].r), L[x] + g[G[x]].w);
}
ld DL(int x) {
    return min(W1(g[G[x]].l, x), R[x] + g[G[x]].w);
}

算法复杂度

• 离散化：$O((N + Q) \log (N + Q))$
• 区间预处理：$O(N \log N)$
• 动态规划：$O(N)$
• 查询处理：$O(Q)$
• 总复杂度：$O((N + Q) \log N)$

算法标签

• 离散化：将大范围坐标映射到小范围索引
• 动态规划：区间内的最短路径计算
• 贪心优化：利用区间结构和扶梯特性
• 双指针技巧：区间填充和处理
• 前缀和：快速计算区间步行时间

总结

这道题的关键在于：

1. 利用离散化处理大范围坐标
2. 将问题分解为区间内的动态规划
3. 巧妙处理扶梯的方向性和组合使用
4. 通过预处理加速查询响应

算法通过精细的状态设计和转移方程，高效解决了大规模数据下的最短路径查询问题。