这是 LeetCode 3244. 新增道路查询后的最短距离 II（困难版）的 Java 实现。
题目分析
本题与简单版（3243）的区别在于数据范围扩大到 `n, queries.length ≤ 10^5`，且关键约束：新增的道路不会交叉（不存在 `queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]`）。
由于道路不交叉，贪心策略成立：遇到捷径就走捷径是最优的。被跳过的城市不可能再出现在最短路径中。
核心思路：区间并查集
将问题转化为维护有效节点集合：
- 初始有 `n` 个城市，最短路径长度为 `n-1`（经过所有边）
- 每新增一条道路 `[u, v]`，相当于可以跳过 `(u, v)` 之间的所有城市
- 使用并查集维护"下一个有效节点"，将区间 `[u, v-1]` 内的节点合并到 `v-1` 的代表元
- 每次合并减少一个连通块，答案就是当前连通块数量
并查集数组含义：`fa[i]` 表示从节点 `i` 出发，下一个未被覆盖的节点（带路径压缩）。
Java 代码
```java
class UnionFind {
public final int[] fa;
public UnionFind(int size) {
fa = new int[size];
// 初始化：每个节点指向自己
for (int i = 1; i < size; i++) {
fa[i] = i;
}
}
public int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]); // 路径压缩
}
return fa[x];
}
}
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
UnionFind uf = new UnionFind(n - 1);
int[] ans = new int[queries.length];
int cnt = n - 1; // 初始连通块数量 = 边数 = n-1
for (int qi = 0; qi < queries.length; qi++) {
int l = queries[qi][0]; // 起点
int r = queries[qi][1] - 1; // 终点前一条边
int fr = uf.find(r); // 找到 r 所在集合的代表元
// 遍历 [l, r) 区间内的所有节点，将它们合并到 fr
for (int i = uf.find(l); i < r; i = uf.find(i + 1)) {
uf.fa[i] = fr; // 直接指向代表元
cnt--; // 每合并一次，连通块数减1
}
ans[qi] = cnt;
}
return ans;
}
}
```
代码解释
关键部分 说明
`fa[i]` 节点 `i` 的父节点，带路径压缩
`find(x)` 查找 `x` 所在集合的代表元
`cnt = n - 1` 初始最短路径经过 `n-1` 条边
`r = queries[qi][1] - 1` 将城市编号转换为边编号（城市 `i` 到 `i+1` 的边编号为 `i`）
`for (int i = uf.find(l); i < r; i = uf.find(i + 1))` 跳跃式遍历，跳过已被合并的节点，均摊 O(1)
复杂度分析
- 时间复杂度：O((n + q) × α(n))，其中 α 是阿克曼函数的反函数，近似常数。每个节点最多被合并一次。
- 空间复杂度：O(n)
另一种思路：贪心 + TreeSet
如果不使用并查集，也可以用 `TreeSet` 维护剩余城市：
```java
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < n; i++) {
set.add(i);
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int l = queries[i][0];
int r = queries[i][1];
// 删除 (l, r) 开区间内的所有城市
// 这些城市被捷径覆盖，不可能出现在最短路径中
Integer cur = set.higher(l); // 第一个大于 l 的元素
while (cur != null && cur < r) {
set.remove(cur);
cur = set.higher(l); // 继续找下一个
}
ans[i] = set.size() - 1; // 剩余节点数 - 1 = 边数
}
return ans;
}
}
```
时间复杂度：O((n + q) log n)，在数据范围较小时也可通过，但并查集版本更优。
