一、问题分析与数学建模

1.1 问题本质

这是一道Dijkstra最短路 + 线段树优化的图论问题，核心在于如何高效处理"矩形区域可达"的特殊边结构。

问题形式化

给定：

• $n$ 座城市，坐标 $(x_i, y_i)$，$1 \le x_i \le w, 1 \le y_i \le h$
• $m$ 个弹跳装置，第 $i$ 个位于城市 $p_i$，花费 $t_i$，可到达矩形 $[L_i, R_i] \times [D_i, U_i]$ 内的任意城市

目标：

• 求从首都（城市 $1$）到所有其他城市的最短路径长度

图论建模：

• 节点：$n$ 座城市
• 边：第 $i$ 个弹跳装置产生若干条边
  • 起点：城市 $p_i$
  • 终点：所有坐标在矩形 $[L_i, R_i] \times [D_i, U_i]$ 内的城市
  • 权值：$t_i$

---

1.2 核心数学观察

观察 1：边数爆炸问题

朴素建图：对于每个弹跳装置，枚举矩形内的所有城市，建立有向边。

问题：

• 最坏情况下，每个弹跳装置可到达 $O(n)$ 座城市
• 总边数：$O(mn)$
• Dijkstra时间复杂度：$O(mn \log m)$
• 对于 $n = 7 \times 10^4, m = 1.5 \times 10^5$，约 $10^{10}$ 次操作，无法接受

---

观察 2：隐式图的性质

关键性质：我们不需要显式地存储所有边，只需要在Dijkstra扩展时，动态查询可达的城市。

Dijkstra的本质：

• 每次取出距离最小的节点 $u$
• 枚举 $u$ 的所有出边 $(u, v, w)$
• 更新 $\text{dis}[v] = \min(\text{dis}[v], \text{dis}[u] + w)$

本题的特殊性：

• 节点不是城市，而是弹跳装置
• 从弹跳装置 $i$ 可以到达矩形内的所有城市
• 到达城市 $u$ 后，可以使用 $u$ 的所有弹跳装置

---

观察 3：状态空间重构

定义状态：

• $\text{dis}[i]$：从首都到达弹跳装置 $i$ 的最短时间（到达装置所在城市，准备使用该装置）
• $\text{ans}[u]$：从首都到达城市 $u$ 的最短时间

状态转移：

1. 初始化：首都（城市 $0$）的所有弹跳装置，$\text{dis}[i] = t_i$
2. 从弹跳装置 $i$（距离 $d$）扩展：
   • 查询矩形 $[L_i, R_i] \times [D_i, U_i]$ 内的所有城市 $u$
   • 更新 $\text{ans}[u] = \min(\text{ans}[u], d)$（到达城市的时间）
   • 对于城市 $u$ 的每个弹跳装置 $j$，更新 $\text{dis}[j] = \min(\text{dis}[j], d + t_j)$

核心优化：每个城市只需要被访问一次。

---

观察 4：避免重复访问

引理 1：如果城市 $u$ 已经被某个弹跳装置访问过，则不需要再被其他弹跳装置访问。

证明：

• 假设弹跳装置 $i$ 和 $j$ 都能到达城市 $u$，且 $\text{dis}[i] < \text{dis}[j]$
• 当装置 $i$ 扩展时，$\text{ans}[u]$ 已经被更新为 $\text{dis}[i]$
• 当装置 $j$ 扩展时，$\text{dis}[j] \ge \text{dis}[i]$，不会更新 $\text{ans}[u]$
• 对于城市 $u$ 的弹跳装置 $k$，$\text{dis}[k]$ 在装置 $i$ 扩展时已经更新
• 因此，装置 $j$ 再次访问城市 $u$ 是冗余的

优化策略：访问过的城市立即从数据结构中删除。

---

二、算法设计与数据结构

2.1 二维矩形查询问题

问题：给定矩形 $[L, R] \times [D, U]$，快速查询其中包含的所有城市，并支持删除操作。

数据结构选择：线段树 + set

结构设计

一维：$x$ 坐标

• 建立线段树，区间 $[0, n-1]$（表示 $x$ 坐标的索引）
• 每个线段树节点对应一个 $x$ 坐标区间

二维：$y$ 坐标

• 在每个线段树节点维护一个 set<pair<int, int>>
• 存储 $(y, \text{城市编号})$ 对，按 $y$ 坐标排序

插入操作：

• 将城市 $u$（坐标 $(x_u, y_u)$）插入线段树
• 在根节点到叶子节点的路径上的所有节点，都插入 $(y_u, u)$

查询操作：

• 查询矩形 $[L, R] \times [D, U]$ 内的城市
• 在线段树中找到覆盖 $[L, R]$ 的所有节点
• 在每个节点的 set 中，用 lower_bound 找到 $y \ge D$ 的城市
• 遍历所有 $y \le U$ 的城市

删除操作：

• 在线段树路径上的所有节点中，删除对应的 $(y, u)$ 对

---

2.2 算法流程

Dijkstra变种

初始化：
    for 首都的每个弹跳装置 i:
        dis[i] = t[i]
        pq.push((-dis[i], i))

while pq 非空:
    取出距离最小的弹跳装置 i
    if vis[i]: continue
    vis[i] = true
    
    查询矩形 [L[i], R[i]] × [D[i], U[i]] 内的所有城市 u:
        ans[u] = min(ans[u], dis[i])
        
        for 城市 u 的每个弹跳装置 j:
            if dis[j] > dis[i] + t[j]:
                dis[j] = dis[i] + t[j]
                pq.push((-dis[j], j))
        
        从线段树中删除城市 u

---

三、代码模块详解

模块 1：数据结构定义

constexpr int inf = 2e9;
using pii = pair<int, int>;

struct rect {
    int l, r, d, u;  // 矩形的左右边界和下上边界
    inline rect() {}
    inline rect(int l, int r, int d, int u) : l(l), r(r), d(d), u(u) {}
};

int n, m, w, h;
vector<pii> a(n);              // a[i] = (x, y): 城市 i 的坐标
vector<set<pii>> S(n << 2);    // 线段树，每个节点存储 set<(y, 城市编号)>
vector<rect> b(m);             // b[i]: 弹跳装置 i 的矩形范围
vector<vector<pii>> que(n);    // que[u]: 城市 u 的所有弹跳装置 (时间, 装置编号)

关键设计：

• S[u]：线段树节点 $u$ 的 set，存储 $(y, \text{城市})$ 对
• que[u]：城市 $u$ 的所有弹跳装置，存储 $(t, i)$ 表示装置 $i$ 花费时间 $t$

---

模块 2：线段树插入操作

auto ls = [&](int u) { return 2 * u + 1; };  // 左儿子
auto rs = [&](int u) { return 2 * u + 2; };  // 右儿子

auto insert = [&](auto &&self, int u, int l, int r, int p) -> void {
    // 在节点 u (区间 [l, r]) 中插入城市 p
    S[u].emplace(a[p].second, p);  // 插入 (y坐标, 城市编号)
    
    if (l == r)  // 叶子节点
        return;
    
    int mid = (l + r) >> 1;
    
    if (a[p].first <= mid)  // x坐标 <= mid，递归左子树
        self(self, ls(u), l, mid, p);
    else  // x坐标 > mid，递归右子树
        self(self, rs(u), mid + 1, r, p);
};

// 插入所有城市
for (int i = 0, x, y; i < n; i++) {
    cin >> x >> y;
    x--, y--;  // 转为 0-indexed
    a[i] = {x, y};
    insert(insert, 0, 0, n - 1, i);
}

算法逻辑：

1. 将城市 $p$ 的 $(y, p)$ 对插入当前节点的 set
2. 如果不是叶子节点，根据 $x$ 坐标递归插入左或右子树
3. 每个城市会被插入到从根到叶子路径上的所有节点

时间复杂度：$O(\log n)$ 每次插入

---

模块 3：读入与预处理

vector<rect> b(m);
vector<vector<pii>> que(n);

for (int i = 0, p, t, l, r, d, u; i < m; i++) {
    cin >> p >> t >> l >> r >> d >> u;
    p--, l--, r--, d--, u--;  // 转为 0-indexed
    b[i] = {l, r, d, u};
    que[p].emplace_back(t, i);  // 城市 p 的弹跳装置 i，花费 t
}

priority_queue<pii> pq;        // 优先队列，存储 (-距离, 装置编号)
vector<int> dis(m, inf);       // dis[i]: 到达弹跳装置 i 的最短时间
vector<int> ans(n, inf);       // ans[u]: 到达城市 u 的最短时间
vector<bool> vis(m);           // vis[i]: 弹跳装置 i 是否已访问

数据结构说明：

• que[p]：记录城市 $p$ 的所有弹跳装置
• dis[i]：到达装置 $i$ 所在城市并准备使用该装置的最短时间
• ans[u]：到达城市 $u$ 的最短时间（可能不使用该城市的任何装置）

---

模块 4：矩形查询与删除（核心）

auto erase = [&](auto &&self, int u, int l, int r, int p) -> void {
    // 在节点 u (区间 [l, r]) 中查询弹跳装置 p 能到达的城市
    
    if (l >= b[p].l && r <= b[p].r) {  // 当前区间完全被矩形包含
        // 在 set 中查询 y 坐标在 [D, U] 范围内的城市
        auto it = S[u].lower_bound(pii{b[p].d, 0});
        
        while (it != S[u].end() && it->first <= b[p].u) {
            int city = it->second;  // 城市编号
            
            // 更新该城市的所有弹跳装置
            for (auto y : que[city]) {
                if (vis[y.second])  // 装置已访问
                    continue;
                
                if (chmin(dis[y.second], dis[p] + y.first)) {
                    pq.emplace(-dis[y.second], y.second);
                }
            }
            
            // 更新到达该城市的最短时间
            chmin(ans[city], dis[p]);
            
            // 从 set 中删除该城市（关键优化！）
            auto tmp = it;
            it++;
            S[u].erase(tmp);
        }
        
        return;
    }
    
    int mid = (l + r) >> 1;
    
    // 递归查询左右子树
    if (b[p].l <= mid)
        self(self, ls(u), l, mid, p);
    
    if (b[p].r > mid)
        self(self, rs(u), mid + 1, r, p);
};

算法流程：

步骤 1：判断当前节点区间是否被矩形完全包含

• 如果 $[l, r] \subseteq [L_p, R_p]$，则该节点内所有 $x$ 坐标都满足条件
• 只需在 set 中查询 $y$ 坐标在 $[D_p, U_p]$ 内的城市

步骤 2：在 set 中查询

• lower_bound(pii{D, 0})：找到第一个 $y \ge D$ 的城市
• 遍历所有 $y \le U$ 的城市

步骤 3：更新距离

• 对于城市 $u$ 的每个弹跳装置 $j$：
  • 如果 $\text{dis}[j] > \text{dis}[p] + t_j$，更新并加入优先队列
• 更新 $\text{ans}[u] = \min(\text{ans}[u], \text{dis}[p])$

步骤 4：删除城市（关键！）

• 从 set 中删除城市 $u$
• 保证每个城市只被访问一次

步骤 5：递归子树

• 如果当前区间不被完全包含，递归查询左右子树

时间复杂度：

• 单次查询：$O(\log n \times k)$，$k$ 是矩形内的城市数
• 总体：每个城市最多被访问一次，均摊 $O(n \log n)$

---

模块 5：Dijkstra主流程

// 初始化：将首都（城市 0）的所有弹跳装置加入队列
for (auto y : que[0]) {
    pq.emplace(-y.first, y.second);  // (-时间, 装置编号)
    dis[y.second] = y.first;
}

// Dijkstra
while (!pq.empty()) {
    pii x = pq.top();
    pq.pop();
    
    int device = x.second;  // 弹跳装置编号
    
    if (vis[device])  // 已访问
        continue;
    
    vis[device] = true;
    
    // 查询该装置能到达的所有城市，并更新距离
    erase(erase, 0, 0, n - 1, device);
}

// 输出答案
for (int i = 1; i < n; i++)
    cout << ans[i] << '\n';

算法逻辑：

初始化：

• 从首都（城市 $0$）出发
• 将城市 $0$ 的所有弹跳装置加入优先队列
• 距离为弹跳装置的时间 $t_i$

主循环：

• 取出距离最小的弹跳装置 $i$
• 如果已访问，跳过
• 标记为已访问
• 调用 erase 查询矩形内的所有城市，更新距离

输出：

• $\text{ans}[i]$ 是从首都到城市 $i$ 的最短时间

---

四、正确性证明

4.1 Dijkstra正确性

定理 1：算法正确计算从首都到所有城市的最短路径。

证明（归纳法）：

基础：首都到自身的距离为 $0$

归纳假设：假设已访问的弹跳装置集合 $V$ 的距离都是正确的。

归纳步骤：

• 取出距离最小的未访问弹跳装置 $i$，距离为 $d$
• 对于任何到达装置 $i$ 的其他路径，必须经过某个未访问的弹跳装置 $j$
• 由于 $\text{dis}[j] \ge \text{dis}[i] = d$（优先队列性质）
• 因此任何其他路径的长度 $\ge d$
• 所以 $\text{dis}[i] = d$ 是正确的

---

4.2 删除操作的正确性

定理 2：每个城市只需要被访问一次。

证明：

• 假设城市 $u$ 第一次被装置 $i$ 访问，距离 $d_i = \text{dis}[i]$
• 第二次被装置 $j$ 访问，距离 $d_j = \text{dis}[j]$
• 由于 Dijkstra 的性质，$d_j \ge d_i$
• 因此 $\text{ans}[u] = d_i$，不会被 $d_j$ 更新
• 对于城市 $u$ 的弹跳装置 $k$：
  • 在装置 $i$ 访问时，$\text{dis}[k] = \min(\text{dis}[k], d_i + t_k)$
  • 在装置 $j$ 访问时，$d_j + t_k \ge d_i + t_k$，不会更新
• 因此第二次访问是冗余的

---

五、复杂度分析

5.1 时间复杂度

线段树构建：

• 插入 $n$ 个城市，每次 $O(\log n)$
• 总时间：$O(n \log n)$

Dijkstra主循环：

• 最多 $m$ 次装置扩展
• 每次装置扩展：
  • 查询矩形：$O(\log n)$ 递归深度
  • 处理城市：每个城市只被处理一次，总共 $O(n)$
  • 更新装置：总共 $O(m)$ 次更新
  • 优先队列操作：$O(m \log m)$

总时间复杂度：$O(n \log n + m \log m)$

对于 $n = 7 \times 10^4, m = 1.5 \times 10^5$，约 $2 \times 10^6$ 次操作，完全可行。

---

5.2 空间复杂度

线段树：

• 节点数：$O(n)$
• 每个节点存储 set，每个城市出现在 $O(\log n)$ 个节点中
• 总空间：$O(n \log n)$

其他：

• 城市坐标、弹跳装置信息：$O(n + m)$
• 距离数组、优先队列：$O(m)$

总空间复杂度：$O(n \log n + m)$

对于 $n = 7 \times 10^4$，约 $7 \times 10^4 \times 17 = 1.2 \times 10^6$ 个 pair<int, int>，约 $20 \text{MB}$，在 $128 \text{MB}$ 限制内。

---

六、算法优化与扩展

6.1 关键优化技巧

优化 1：惰性删除

• 不在插入时删除，只在访问时删除
• 避免维护复杂的删除操作

优化 2：状态重构

• 不直接在城市之间建边
• 而是在弹跳装置之间建立转移关系
• 减少了状态空间

优化 3：每个城市只访问一次

• 访问后立即从线段树中删除
• 保证总访问次数 $O(n)$

优化 4：二维查询拆分

• $x$ 坐标：线段树区间查询
• $y$ 坐标：set + lower_bound
• 避免了复杂的二维数据结构

---

6.2 特殊情况优化

情况 1：$h = 1$（一维问题）

• 退化为一维区间查询
• 可以用简单的排序 + 双指针

情况 2：每个装置只到达一个城市

• 退化为普通的最短路问题
• 可以直接用 Dijkstra + 邻接表

---

七、知识点总结

7.1 核心算法技巧

1. ✅ Dijkstra最短路

   • 在隐式图上运行
   • 状态重构：装置而非城市

2. ✅ 线段树 + set

   • 二维矩形查询
   • 支持动态删除

3. ✅ 图论建模

   • 隐式图：不显式存储边
   • 动态查询邻接节点

4. ✅ 时间空间权衡

   • 用额外空间（线段树）换取时间效率
   • 每个城市只访问一次

5. ✅ 数据结构设计

   • 组合多种数据结构
   • 充分利用各自优势

---

7.2 适用场景

• ✅ 图的边数过多，无法显式存储
• ✅ 边具有规则结构（矩形区域）
• ✅ 最短路问题 with 特殊边结构
• ✅ 需要高效的二维查询和删除

---

八、总结

8.1 算法精髓

本题采用的Dijkstra + 线段树算法的核心思想：

1. 问题转化：将城市间的最短路转化为装置间的最短路
2. 隐式图：不显式建边，动态查询可达节点
3. 高效查询：用线段树 + set 实现 $O(\log n)$ 的二维矩形查询
4. 避免重复：每个城市只访问一次，访问后立即删除
5. 状态设计：$\text{dis}[i]$ 表示到达装置，$\text{ans}[u]$ 表示到达城市