卓老师建站网站后台如何直接登陆,太平洋建设集团网站,广东深圳网站建设微信商城开发,望野的翻译执行结果#xff1a;通过 题目#xff1a;3244 新增道路查询后的最短距离II
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市#xff0c;编号从 0 到 n - 1。初始时#xff0c;每个城市 i 都有一条单向道路通往城市 i 1#xff08; 0 i n - 1…执行结果通过 题目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] 中的每个 ianswer[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 1051 queries.length 105queries[i].length 20 queries[i][0] queries[i][1] n1 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,l2,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,r1,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
解题思路
初始化线段树 创建一个 LazySegmentTree 实例其大小为 4n因为线段树通常需要一个额外的空间来存储内部节点。初始化 cnt 数组来存储每个节点的区间内未访问元素的数量。初始化 todo 数组来存储延迟的更新操作。调用 build 方法来构建线段树初始时所有元素都是未访问的所以每个叶子节点的 cnt 值都设为 1表示该位置是未访问的。处理查询 对于每个查询 (l, r)调用 update 方法将索引从 l2 到 r注意这里的 l2 是因为题目可能有特定的索引约定比如索引 0 和 1 被视为特殊情况或者为了避免边界问题之间的所有元素标记为已访问即将其 cnt 值更新为 0。在每次更新后通过查看根节点的 cnt 值即整个数组的未访问元素数量减 1 来计算最近的未访问元素与数组起始位置的距离。这是因为每次更新都会使得一个元素从未访问变为已访问而根节点的 cnt 值反映了整个数组中未访问元素的数量。减 1 是因为索引是从 0 开始的而我们需要的是距离所以需要将计数器的值转换为实际的索引距离这里假设数组中的元素是连续排列的没有空缺。线段树的操作 build 方法用于构建线段树初始化每个叶子节点的 cnt 值。maintain 方法用于维护节点的 cnt 值确保它反映了其子节点的 cnt 值之和。do 方法用于立即更新节点的 cnt 值和 todo 值。spread 方法用于将延迟的更新操作传播到子节点。update 方法用于执行区间更新操作使用延迟技术来优化性能。query 方法虽然在这段代码中未使用但通常用于查询区间内的某些信息如最大值、最小值等。
