3244. Shortest Distance After Road Addition Queries II

You are given an integer n and a 2D integer array queries.

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.

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.

There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].

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.

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        map<int,int> mp;
        vector<int> res;
        for(int i = 0; i < n - 1; i++) mp[i] = i + 1;
        int now = n - 1;
        for(auto& q : queries) {
            int u = q[0], v = q[1];
            
            if(mp.count(u) and mp[u] < v) {
                auto it = mp.lower_bound(u);
                it->second = v;
                auto nit = next(it);
                while(nit != end(mp) and nit->first < v) {
                    now -= 1;
                    auto nnit = next(nit);
                    mp.erase(nit);
                    nit = nnit;
                }
            }
           
            res.push_back(now);
        }
        return res;
    }
};