Burnling's Blog
0%

LeetCode 周赛409Q3 新增道路查询后的最短距离 II

发表于 更新于 分类于 ，

题目链接

思路分析

题目不好好读完是这样的。

提示中提到，不存在两个查询都满足 i != j 且 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

也就是说，两条新增道路之间的关系仅有被包含与不相交，不存在相交的区间。

那么对于一条新添加的 $u\to v$ 的边，它可以替代掉起终点落在 $[u,v]$ 区间内的所有边。

模拟即可。复杂度为 $O(n)$。因为至多删掉 $n-1$ 条边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    set<pair<int,int>> G;
    vector<int> lftp;

    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int> ans;
        for(int i = 1;i<n;i++) G.insert(make_pair(i,i+1));
        
        for(auto query : queries){
            int u = query[0] + 1;
            int v = query[1] + 1;

            auto it = G.lower_bound(make_pair(u,-1)); //找到第一条

            if(it != G.end() && it->first == u && it->second < v){
                while(it != G.end() && it->first < v) it = G.erase(it);
                G.insert(make_pair(u,v));
            }

            ans.push_back(G.size());
        }
        return ans;
    }
};