3244. Shortest Distance After Road Addition Queries II Hard

1/**
2 * [3244] Shortest Distance After Road Addition Queries II
3 *
4 * You are given an integer n and a 2D integer array queries.
5 * There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.
6 * queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1.
7 * There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].
8 * Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 5, queries = [[2,4],[0,2],[0,4]]</span>
13 * Output: <span class="example-io">[3,2,1]</span>
14 * Explanation: 
15 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image8.jpg" style="width: 350px; height: 60px;" />
16 * After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
17 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image9.jpg" style="width: 350px; height: 60px;" />
18 * After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
19 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image10.jpg" style="width: 350px; height: 96px;" />
20 * After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">n = 4, queries = [[0,3],[0,2]]</span>
25 * Output: <span class="example-io">[1,1]</span>
26 * Explanation:
27 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image11.jpg" style="width: 300px; height: 70px;" />
28 * After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
29 * <img alt="" src="https://assets.leetcode.com/uploads/2024/06/28/image12.jpg" style="width: 300px; height: 70px;" />
30 * After the addition of the road from 0 to 2, the length of the shortest path remains 1.
31 * </div>
32 *  
33 * Constraints:
34 * 
35 * 	3 <= n <= 10^5
36 * 	1 <= queries.length <= 10^5
37 * 	queries[i].length == 2
38 * 	0 <= queries[i][0] < queries[i][1] < n
39 * 	1 < queries[i][1] - queries[i][0]
40 * 	There are no repeated roads among the queries.
41 * 	There are no two queries such that i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/shortest-distance-after-road-addition-queries-ii/
47// discuss: https://leetcode.com/problems/shortest-distance-after-road-addition-queries-ii/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
53        vec![]
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3244() {
65    }
66}
67