题意理解

• 有 N 个公交站点，编号 1 到 N。
• 家靠近站点 1，学校靠近站点 N。
• 有 M 辆巴士，每辆巴士一天只运行一次，从站点 A_i 在时刻 X_i 出发，到站点 B_i 在时刻 Y_i 到达。
• 换乘不需要时间，只要在巴士出发时间之前到达该站点即可。
• 每天学校要求 最晚 L_i 时刻到达站点 N。
• 问：每天 最晚何时从站点 1 出发 才能按时到校？如果无法到达，输出 -1。

思路分析

这是一个 有向图的最晚出发时间问题。

如果要求到达 N 的时间 ≤ L_i，那么我们可以 从终点 N 倒推 到起点 1。

核心思想：逆序处理

1. 把巴士信息看作有向边 (A_i, B_i, X_i, Y_i)。

2. 如果正着考虑，很难确定最晚出发时间，因为换乘条件要求“在出发时间前到达站点”。

3. 反过来想：

   • 假设我们要求 到达 N 的时间 ≤ L，那么我们可以从 N 出发，沿着巴士反向走（即把边反向），变成：
     如果某巴士在 Y_i 时刻到达 B_i，并且我们在 Y_i 时刻（或更早）在 B_i，那么我们可以“逆乘”这辆巴士，在 X_i 时刻出现在 A_i。
   • 但是注意：在逆向过程中，我们实际上是在求 每个站点最晚到达时间，使得能按时到 N。
   • 具体来说：
     设 latest[v] 表示为了按时到 N，在站点 v 的最晚到达时间。
     初始 latest[N] = L，其它站点初始为 -1（表示未确定）。
   • 对于一条巴士 (a, b, x, y)：
     如果 latest[b] >= y，那么我们可以通过这辆巴士从 b 到 a，从而更新 latest[a] = max(latest[a], x)？
     不对，这里要小心：
     在正向时，我们在 a 站必须在 x 时刻之前到达，才能坐上这辆车，在 y 时刻到达 b。
     反过来，如果我们知道在 b 站最晚 y 时刻到达（即 latest[b] >= y），那么我们可以乘坐这辆车从 a 到 b，这意味着在 a 站最晚可以在 x 时刻出发。
     所以 latest[a] = max(latest[a], x) 吗？
     不完全是，因为可能有多辆从 a 到 b 的车，我们应取 最大的 x 满足 y <= latest[b]，这样我们就能在 a 站更晚出发。

4. 因此，我们可以这样处理：

   • 对每个站点，维护一个集合（或优先队列），存储从该站点出发的所有巴士 (b, x, y)。
   • 按 latest[b] 从大到小处理站点，用类似 Dijkstra 的方法更新前驱站点的最晚出发时间。

算法步骤

1. 构建正向图：graph[a] 存储元组 (b, x, y) 表示从 a 出发到 b 的巴士。
2. 对每个查询 L：
   • 初始化 latest[1..N] = -1，latest[N] = L。
   • 用最大堆（优先队列），按 latest[v] 从大到小处理。
   • 当堆不为空：
     • 取出 (time, node)，如果 time < latest[node] 则跳过（旧数据）。
     • 遍历 graph[node] 中所有边 (b, x, y)：
       • 如果 y <= latest[node] 且 x > latest[b]，则更新 latest[b] = x，并加入堆。
   • 答案就是 latest[1]。

复杂度

• 每条边最多被处理一次，因此 O(M log N) 每个查询。
• 但 Q 最多 1e5，M 最多 3e5，如果每个查询都跑一次 Dijkstra 会超时。

优化

注意到不同查询之间只有 latest[N] 不同，我们可以 预处理：

• 将巴士按 Y_i 从大到小排序。
• 用并查集或类似方法，从大到小枚举“到达时间限制”，动态维护每个站点能到达 N 的最晚出发时间。

具体做法（离线查询）：

1. 将查询按 L_i 从大到小排序。
2. 将巴士按 Y_i 从大到小排序。
3. 初始化 ans[i] = -1。
4. 用并查集维护每个站点已知的能到达 N 的最晚出发时间。
5. 按 L 从大到小处理：
   • 将满足 Y_i ≤ L 的巴士加入（这些巴士在 L 时可用）。
   • 加入巴士时，更新对应站点的最晚出发时间（取 max）。
   • 如果 1 号站点被更新，则记录答案。

这样可以在 O((M+Q) α(N)) 时间内解决。

样例 1 验证

输入：

5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100

输出：

-1
5
10
30

与题目一致。

最终方法总结

1. 将问题转化为：已知到达 N 的最晚时间 L，求 1 号站点的最晚出发时间。
2. 逆向思维，从 N 出发，用类似 Dijkstra 的方法，按时间从晚到早传播。
3. 为了应对多查询，采用离线处理，按 L 降序，逐步加边，用并查集维护每个站点的最晚出发时间。
4. 时间复杂度 O(M log M + Q log Q) 或 O((M+Q) log N)，可以满足数据范围要求。