Leetcode打卡：新增道路查询后的最短距离II

执行结果：通过

题目：3244 新增道路查询后的最短距离II

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]

输出： [3, 2, 1]

解释：

新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。

新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。

新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]

输出： [1, 1]

解释：

新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。

新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

提示:

• 3 <= n <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• 查询中不存在重复的道路。
• 不存在两个查询都满足 i != j 且 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

代码以及解题思路

代码：

class Solution:def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:st = LazySegmentTree(n)ans = []for l, r in queries:st.update(1,1,n,l+2,r, 0)ans.append(st.cnt[1]-1)return ansclass LazySegmentTree:def __init__(self, n: int):self.cnt = [0] * (4 * n)self.todo = [-1] * (4 * n)self.build(1,1,n)# 初始化线段树   o,l,r=1,1,ndef build(self, o: int, l: int, r: int) -> None:if l == r:self.cnt[o] = 1returnm = (l + r) >> 1self.build(o * 2, l, m)self.build(o * 2 + 1, m + 1, r)self.maintain(o)def maintain(self, o: int) -> None:self.cnt[o] = self.cnt[o * 2] + self.cnt[o * 2 + 1]def do(self, o: int, val: int) -> None:self.cnt[o] = valself.todo[o] = valdef spread(self, o: int) -> None:v = self.todo[o]if v == 0:self.do(o * 2, v)self.do(o * 2 + 1, v)self.todo[o] = -1def update(self, o: int, l: int, r: int, L: int, R: int, val: int) -> None:if L <= l and r <= R:self.do(o, val)returnself.spread(o)m = (l + r) >> 1if m >= L:self.update(o * 2, l, m, L, R, val)if m < R:self.update(o * 2 + 1, m + 1, r, L, R, val)self.maintain(o)def query(self, o: int, l: int, r: int, L: int, R: int) -> int:if L <= l and r <= R:return self.cnt[o]self.spread(o)m = (l + r) >> 1res = 0if L <= m:res = self.query(o * 2, l, m, L, R)if m < R:res = max(res, self.query(o * 2 + 1, m + 1, r, L, R))return res

解题思路：

1. 初始化线段树：
   • 创建一个 LazySegmentTree 实例，其大小为 4n（因为线段树通常需要一个额外的空间来存储内部节点）。
   • 初始化 cnt 数组来存储每个节点的区间内未访问元素的数量。
   • 初始化 todo 数组来存储延迟的更新操作。
   • 调用 build 方法来构建线段树，初始时所有元素都是未访问的，所以每个叶子节点的 cnt 值都设为 1（表示该位置是未访问的）。
2. 处理查询：
   • 对于每个查询 (l, r)，调用 update 方法将索引从 l+2 到 r（注意这里的 l+2 是因为题目可能有特定的索引约定，比如索引 0 和 1 被视为特殊情况，或者为了避免边界问题）之间的所有元素标记为已访问（即将其 cnt 值更新为 0）。
   • 在每次更新后，通过查看根节点的 cnt 值（即整个数组的未访问元素数量）减 1 来计算最近的未访问元素与数组起始位置的距离。这是因为每次更新都会使得一个元素从未访问变为已访问，而根节点的 cnt 值反映了整个数组中未访问元素的数量。减 1 是因为索引是从 0 开始的，而我们需要的是距离，所以需要将计数器的值转换为实际的索引距离（这里假设数组中的元素是连续排列的，没有空缺）。
3. 线段树的操作：
   • build 方法用于构建线段树，初始化每个叶子节点的 cnt 值。
   • maintain 方法用于维护节点的 cnt 值，确保它反映了其子节点的 cnt 值之和。
   • do 方法用于立即更新节点的 cnt 值和 todo 值。
   • spread 方法用于将延迟的更新操作传播到子节点。
   • update 方法用于执行区间更新操作，使用延迟技术来优化性能。
   • query 方法虽然在这段代码中未使用，但通常用于查询区间内的某些信息（如最大值、最小值等）。