题解：大平原最短路径问题

算法标签

• 扫描线算法
• 线段树优化
• 动态规划
• 坐标离散化
• 曼哈顿距离

问题分析

这个问题要求计算蚂蚁从起点到终点的最短移动时间，其中：

• 平原区域移动速度为 100 分钟/公里
• 丘陵区域（矩形内部）移动速度为 w 分钟/公里
• 只能沿坐标轴方向移动

核心思路

1. 问题简化

由于只能沿坐标轴移动，问题可以分解为：

• 水平移动：从 x₁ 到 x₂
• 垂直移动：从 y₁ 到 y₂

关键观察：最优路径必然由水平线段和垂直线段组成，且转折点只可能出现在矩形边界或起点终点。

2. 算法框架

代码采用扫描线 + 线段树优化的方法：

步骤1：坐标离散化

vector<int> v = {src.second, dst.second};
for (int i = 0; i < n; i++) {
    v.push_back(p1[i].second);
    v.push_back(p2[i].second);
}
sort(v.begin(), v.end());

• 将所有 y 坐标离散化，减少状态空间
• 便于线段树操作

步骤2：事件处理

将矩形边界作为扫描线事件：

• 进入事件：矩形左边界，更新可达性
• 离开事件：矩形右边界，更新累积代价

步骤3：线段树维护

维护三个线段树：

• seg1：存储当前最小代价
• seg2：存储 代价 - 100*y，用于处理向上移动
• seg3：存储 代价 + 100*y，用于处理向下移动

3. 关键优化

代价传递

当遇到矩形左边界时：

lint lmin = seg3.query(i.l, i.r, 0, v.size() - 1, 1) - 100ll * v[i.l];
lint rmin = seg2.query(i.l, i.r, 0, v.size() - 1, 1) + 100ll * v[i.r];
upload(i.l, lmin);
upload(i.r, rmin);

• 从矩形内部任意点传递代价到边界点
• 利用预计算的 seg2 和 seg3 快速计算

代价累积

当遇到矩形右边界时：

seg1.add(i.l + 1, i.r - 1, 0, v.size() - 1, 1, i.update);
seg2.add(i.l + 1, i.r - 1, 0, v.size() - 1, 1, i.update);
seg3.add(i.l + 1, i.r - 1, 0, v.size() - 1, 1, i.update);

• 为矩形内部区域添加累积代价
• i.update = (p2[i].first - p1[i].first) * (w[i] - 100)

4. 对称处理

由于问题在 x 和 y 方向对称，代码执行两次：

• 第一次：正常方向
• 第二次：交换 x 和 y 坐标后再次计算

复杂度分析

• 离散化：O(N log N)
• 事件排序：O(N log N)
• 线段树操作：每个事件 O(log N)
• 总复杂度：O(N log N)

算法优势

1. 高效处理大规模数据：利用线段树将复杂度从 O(N²) 降为 O(N log N)
2. 精确代价计算：考虑矩形内部不同移动速度的影响
3. 完备性：处理所有可能的路径情况

适用场景

这种扫描线+线段树的组合方法适用于：

• 二维平面上的最短路径问题
• 区域具有不同权值的情况
• 需要高效处理大规模输入的场景

该算法巧妙地将几何问题转化为序列处理问题，通过离散化和线段树实现了高效求解。