admin LV 2 SU @ 2026-9-26 12:01:44

满分解法（100 分）

只需关注两个端点

支付一枚金币会同时得到一段钥匙，后面又可以从已打开的许多宝箱中任选金币。直接记录已经支付过的金币集合，状态数会很大。

先看已打开宝箱的形状。初始为 $[s,s]$ 。若当前已打开 $[l,r]$ ，支付其中的金币 $i$ ，由于 $L_i\le i\le R_i$ ，新获得的区间与 $[l,r]$ 一定相交，打开后的范围恰为

[\min(l,L_i),\max(r,R_i)].

所以已打开的宝箱始终构成一个连续区间。只要宝箱 $1$ 和 $n$ 都已打开，中间就全部打开了。

当 $n=1$ 时，初始钥匙已经足够，答案为 $0$ 。下面讨论 $n>1$ 。

打开一个端点是最短路

建立一个概念上的有向图：对于每个 $i$ ，向每个 $j\in[L_i,R_i]$ 连一条权值为 $1$ 的边。边 $i\to j$ 表示支付金币 $i$ ，从而能够打开宝箱 $j$ 。记这个图上的最短距离为 $\delta(x,y)$ ，不可达时为 $+\infty$ 。

一条从 $x$ 到 $y$ 的路径给出打开宝箱 $y$ 的合法过程：按路径依次取得并支付金币，终点宝箱只需打开，不必支付它的金币。反过来，沿着“宝箱是由哪枚金币首次打开的”向前追溯，可以从任意打开 $y$ 的过程提取这样一条路径。因此单个目标的最优代价就是最短距离。

但不能直接把到两个端点的最短距离相加：两条路径可能共用已经支付的金币。

例如 $n=5,s=3$ ，五个区间依次为 $[1,1],[1,2],[2,4],[4,5],[5,5]$ 。打开左端点可以依次支付金币 $3,2$ ，打开右端点可以依次支付金币 $3,4$ 。独立相加得到 $4$ ，而实际过程如下：

支付的金币	已打开的区间	累计支付
尚未支付	$[3,3]$	$0$
$3$	$[2,4]$	$1$
$2$	$[1,4]$	$2$
$4$	$[1,5]$	$3$

金币 $3$ 同时帮助了两侧，应该只算一次。

找到两条路径共用到哪里

为了准确计算共享的金币，定义：

$a(v)$ ：初始拥有宝箱 $v$ 的钥匙，要求支付金币 $v$ ，最终打开宝箱 $1$ 所需的最少金币数。
$b(v)$ ：同样要求支付金币 $v$ ，但目标改为宝箱 $n$ 。

这个“要求支付金币 $v$ ”很关键。即使 $v=1$ ，仍有 $a(1)=1$ ；类似地 $b(n)=1$ 。这样，两条分支都包含分岔处的同一枚金币，可以统一扣除重复。

设最后一次负责取得宝箱 $1$ 钥匙的金币为 $t$ ，必有 $L_t=1$ 。先到达 $t$ ，再支付它，得到

a(v)=\min_{t:L_t=1}\bigl(\delta(v,t)+1\bigr).

同理，

b(v)=\min_{t:R_t=n}\bigl(\delta(v,t)+1\bigr).

两式均可在反图上用多源最短路求出：计算 $a$ 时，把所有满足 $L_t=1$ 的点距离设为 $1$ ，其余设为无穷；计算 $b$ 时换成 $R_t=n$ 。反图的一条边 $u\to v$ 存在，当且仅当 $u\in[L_v,R_v]$ ，边权仍为 $1$ 。

现在固定一个分岔点 $v$ 。先从 $s$ 到达它，再分别打开两个端点，金币数的上界为

\delta(s,v)+a(v)+b(v)-1.

最后的 $-1$ 扣掉两条分支都支付的金币 $v$ 。若所选路径还存在别的重合，已经支付过的金币可以跳过，不会增加代价：它提供的钥匙已经全部拿到了。

为什么只考虑一个分岔点就足够？从任意最优操作过程中，给每个非初始宝箱记录首次打开它的金币编号作为父亲。父亲对应的宝箱一定更早打开，因此这些关系形成一棵以 $s$ 为根的树。只保留通向宝箱 $1$ 、 $n$ 的两条根路径，它们具有一段公共前缀，并在最后一个公共宝箱 $v$ 处分开；一个端点也可能就是 $v$ 。

公共前缀可以用最短路径替代。两侧路径的代价分别不小于 $a(v)$ 、 $b(v)$ ，并且共同支付的金币 $v$ 只计一次。如果一个端点就是 $v$ ，仍将支付 $v$ 的那一枚计入这条分支；它本来就必须为另一条非空分支支付。这给出了不超过原最优方案的上述表达式。

另一方面，每个表达式都能按前述路径组合成一个代价不超过它的合法方案。两边合起来，答案恰为

$$\operatorname{ans}(s)=\min_v\bigl(\delta(s,v)+a(v)+b(v)-1\bigr).$$

只考虑 $a(v),b(v)$ 均有限的 $v$ 。令 $c(v)=a(v)+b(v)-1$ ，在反图上把各个 $v$ 的初始距离设为 $c(v)$ ，再做一次多源最短路，就同时得到了所有起点的答案。无有限距离的起点输出 $-1$ 。

不显式列出所有区间边

图最多有 $\sum_i(R_i-L_i+1)=O(n^2)$ 条边，不能逐条存储。我们要支持的反图操作是：当点 $u$ 的最短距离确定后，找出所有包含 $u$ 的区间 $[L_v,R_v]$ ，尝试用距离加 $1$ 更新 $v$ 。

在编号轴 $[1,n]$ 上建立一棵线段树。把每个区间 $[L_v,R_v]$ 分解为 $O(\log n)$ 个线段树节点，在这些节点的列表中存下编号 $v$ 。

点 $u$ 属于某个线段树节点代表的区间，当且仅当该节点在 $u$ 对应叶子到根的路径上。因此，当 $u$ 从最小堆中有效弹出时，沿这条路径访问各节点，就能找到需要松弛的反向边。

还必须避免反复扫描同一个列表。某个线段树节点第一次被访问时，当前 $u$ 是它所覆盖的点中，最早确定最短距离的一个。Dijkstra 按最终距离非降顺序弹出点，故以后该区间内的点距离都不会更小。列表中的每个目标都只接收“该距离加 $1$ ”的转移；这次松弛后，再扫描这个列表不可能得到更好的值。因此每次最短路运行中，每个列表只扫描一次。

代码用标记记录已经扫描的线段树节点。沿祖先链遇到已标记节点时可以直接停止：第一次处理这个节点时，更上方的祖先也已经处理过，或因更早的标记而停止，它们同样不会遗漏。三次最短路分别重新初始化标记，列表本身保持不变。

实现顺序与复杂度

先读入所有区间，建立线段树节点列表和每个编号对应的叶子。随后依次计算 $a$ 、 $b$ ，并以有限的 $a(v)+b(v)-1$ 初始化第三次最短路。最后按原输入顺序输出询问答案；不需要询问有序或互不相同。

代码中的 left/right 保存区间，g 保存线段树节点列表，leaf 定位叶子，dijkstra 执行一次反向多源搜索。初始距离不同，所以用最小堆维护处理次序；出堆时跳过已过期的距离快照。

每个区间分解后共存储 $O(n\log n)$ 个编号。一次搜索扫描每个列表一次，总计 $O(n\log n)$ 次检查。对某个真实点 $v$ ，第一次遇到区间 $[L_v,R_v]$ 中已确定的点时，就取得所有这类前驱中最小的距离；它们的边权都是 $1$ ，所以后续前驱不能再次改进 $v$ 。因此每个点除初始入堆外至多再因一次改进入堆，堆操作总计 $O(n\log n)$ 。

时间复杂度： $O(n\log n+q)$ ，包括建表、三次最短路和输出。

空间复杂度： $O(n\log n)$ ，主要为线段树节点列表；距离、标记和堆额外占用 $O(n)$ 空间。

AC 代码（C++20）

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

void solve() {
  int n;
  cin >> n;
  vector<int> left(n + 1), right(n + 1);
  for (int i = 1; i <= n; i++) cin >> left[i] >> right[i];
  vector<vector<int>> g(4 * n);
  vector<int> leaf(n + 1);
  auto build = [&](auto&& self, int p, int l, int r) -> void {
    if (l == r) {
      leaf[l] = p;
      return;
    }
    int mid = (l + r) / 2;
    self(self, p * 2, l, mid);
    self(self, p * 2 + 1, mid + 1, r);
  };
  build(build, 1, 1, n);
  auto add = [&](auto&& self, int p, int l, int r, int u) -> void {
    if (left[u] <= l && r <= right[u]) {
      g[p].push_back(u);
      return;
    }
    int mid = (l + r) / 2;
    if (left[u] <= mid) self(self, p * 2, l, mid, u);
    if (right[u] > mid) self(self, p * 2 + 1, mid + 1, r, u);
  };
  for (int i = 1; i <= n; i++) add(add, 1, 1, n, i);

  constexpr int inf = INT_MAX / 2;
  auto dijkstra = [&](vector<int> dist) {
    using state = pair<int, int>;
    priority_queue<state, vector<state>, greater<state>> pq;
    for (int i = 1; i <= n; i++) {
      if (dist[i] != inf) pq.push({dist[i], i});
    }
    vector<char> used(4 * n);
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (d != dist[u]) continue;
      for (int p = leaf[u]; p && !used[p]; p /= 2) {
        used[p] = true;
        for (int v : g[p]) {
          int nd = d + 1;
          if (nd >= dist[v]) continue;
          dist[v] = nd;
          pq.push({nd, v});
        }
      }
    }
    return dist;
  };
  vector<int> a(n + 1, inf), b(n + 1, inf);
  for (int i = 1; i <= n; i++) {
    if (left[i] == 1) a[i] = 1;
    if (right[i] == n) b[i] = 1;
  }
  a = dijkstra(a);
  b = dijkstra(b);
  vector<int> dist(n + 1, inf);
  for (int i = 1; i <= n; i++) {
    if (a[i] != inf && b[i] != inf) dist[i] = a[i] + b[i] - 1;
  }
  dist = dijkstra(dist);
  int q;
  cin >> q;
  while (q--) {
    int s;
    cin >> s;
    cout << (n == 1 ? 0 : dist[s] == inf ? -1 : dist[s]) << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

0

admin LV 2 SU @ 2026-9-26 12:01:43

直接建立全部区间边（通过子任务 2–4、6，共 50 分）

本方法利用 $M=\sum_i(R_i-L_i+1)$ 较小，覆盖第 $6$ 组；当 $n\le2500$ 时 $M\le n^2$ ，也覆盖第 $2,3,4$ 组。

两端目标与三次搜索

已打开的宝箱始终构成区间：每次购买的区间包含金币所在宝箱，必与旧区间相交。因此目标等价于打开宝箱 $1,n$ 。 $n=1$ 单独回答 $0$ 。

在图中从 $i$ 向所有 $j\in[L_i,R_i]$ 连单位边，表示支付金币 $i$ 后打开 $j$ 。记最短距离为 $\delta$ 。只要求到达一个宝箱时，支付过程中的首次打开依赖链就是一条这样的路径，所以最小代价可用最短路计算。

为处理两条路径共享金币，定义 $a(v)$ 为从宝箱 $v$ 出发、要求支付金币 $v$ 后打开 $1$ 的最小代价， $b(v)$ 则以打开 $n$ 为目标。最后打开 $1$ 的金币必须满足 $L_t=1$ ，从而

$$a(v)=\min_{t:L_t=1}(\delta(v,t)+1),\qquad b(v)=\min_{t:R_t=n}(\delta(v,t)+1).$$

把原图反向，分别将上述两类源点的初始距离设为 $1$ ，就能用两次最短路求出所有 $a,b$ 。不可达值为无穷。要求支付首枚金币意味着 $a(1)=b(n)=1$ ，不能把它们设为零。

一个实际方案中，给每个宝箱记下首次打开它的父亲金币，得到一棵以起点为根的树。通向 $1,n$ 的两条根路径有一段公共前缀，并在某个 $v$ 处分开。公共前缀代价至少为 $\delta(s,v)$ ，两个分支的代价至少为 $a(v),b(v)$ ，但金币 $v$ 只支付一次，所以

$$\operatorname{ans}(s)=\min_v\bigl(\delta(s,v)+a(v)+b(v)-1\bigr).$$

等号另一方向也成立：先沿路径到 $v$ ，再执行两条分支，重复使用的金币无需再次支付，就能打开两个端点。若一个端点正好是 $v$ ，它对应的分支只计强制支付 $v$ 的一枚金币，仍然由减一正确合并。

例如从宝箱 $3$ 出发，其区间为 $[2,4]$ ，金币 $2$ 的区间为 $[1,2]$ ，金币 $4$ 的区间为 $[4,5]$ 。到两端各需两枚，但金币 $3$ 只用一次，总共三枚，这正是 $2+2-1$ 。

令所有有限的 $a(v)+b(v)-1$ 为初始距离，再在反图上做第三次最短路，就同时获得全部起点的答案。结果为无穷时输出 $-1$ 。

按区间逐条建立反向边

对每个 $i$ ，枚举 $j=L_i,L_i+1,\ldots,R_i$ ，把反向边 $j\to i$ 加入邻接表，边权均为 $1$ 。这样共存储 $M$ 条边。第 $6$ 组保证 $M\le2\times10^6$ ，能够直接存储和遍历。

三次搜索均采用最小堆 Dijkstra：所有有限的初始距离入堆；弹出最小距离快照，过期则跳过，否则沿邻接表松弛。初值可能不同，不能将所有源点直接放进普通 BFS 队列而忽略初始代价。

每次搜索中，每条边只在其起点的距离确定后扫描一次。由于边权统一为 $1$ ，某个点第一次收到来自已确定前驱的候选值时，这个前驱的距离已是所有前驱中最小的；后来的前驱不能再改进它。因此每个点除初始入堆外至多因改进入堆一次，堆操作为 $O(n\log n)$ 。

时间复杂度： $O(M+n\log n+q)$ ，包含建图、三次搜索和查询。

空间复杂度： $O(M+n)$ 。

本方法对任意合法区间仍在计算同一张图，没有截断过长区间；只是当 $M$ 达到 $O(n^2)$ 且 $n$ 很大时，建图的时间和内存无法满足限制，需要满分解的区间表示。

参考代码（C++20）

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

void solve() {
  int n;
  cin >> n;
  vector<int> left(n + 1), right(n + 1);
  for (int i = 1; i <= n; i++) cin >> left[i] >> right[i];
  vector<vector<int>> g(n + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = left[i]; j <= right[i]; j++) g[j].push_back(i);
  }
  constexpr int inf = INT_MAX / 2;
  auto dijkstra = [&](vector<int> dist) {
    using state = pair<int, int>;
    priority_queue<state, vector<state>, greater<state>> pq;
    for (int i = 1; i <= n; i++) {
      if (dist[i] != inf) pq.push({dist[i], i});
    }
    while (!pq.empty()) {
      auto [d, u] = pq.top();
      pq.pop();
      if (d != dist[u]) continue;
      for (int v : g[u]) {
        int nd = d + 1;
        if (nd >= dist[v]) continue;
        dist[v] = nd;
        pq.push({nd, v});
      }
    }
    return dist;
  };
  vector<int> a(n + 1, inf), b(n + 1, inf);
  for (int i = 1; i <= n; i++) {
    if (left[i] == 1) a[i] = 1;
    if (right[i] == n) b[i] = 1;
  }
  a = dijkstra(a);
  b = dijkstra(b);
  vector<int> dist(n + 1, inf);
  for (int i = 1; i <= n; i++) {
    if (a[i] != inf && b[i] != inf) dist[i] = a[i] + b[i] - 1;
  }
  dist = dijkstra(dist);
  int q;
  cin >> q;
  while (q--) {
    int s;
    cin >> s;
    cout << (n == 1 ? 0 : dist[s] == inf ? -1 : dist[s]) << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

0

admin LV 2 SU @ 2026-9-26 12:01:43

稠密图上的三次最短路（通过子任务 2–4，共 35 分）

本方法覆盖 $n\le2500$ 的第 $2,3,4$ 组。

把两端目标合并