摘要
Title: 3244. 新增道路查询后的最短距离 II
Categories: 最短路、区间并查集

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

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. 并查集
   https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-ii/solutions/2868558/qu-jian-bing-cha-ji-pythonjavacgo-by-end-a9k7/
   区间并查集，每个边抽象为一个集合，期间维护集合数量
   比如加[l, r]的边，那就是将区间的集合全部和[r-1, r]这个集合合并，注意这里说的是集合，也就是这个集合的根部合并即可，集合里的也就都合并了

2. 贪心
   所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。 是很重要的性质，也就是不会出现区间重合的情况，之后是完全包含，或者完全不包含
   所以可以贪心考虑：对于任意一条从 0 到 (n−1) 的路径，如果里面存在多个小区间可以被一个大区间包含，那么直接把它们替换成这个大区间，答案会变得更好。
   因此我们可以用一个 set 维护当前的最短路包含哪些区间。加入一个区间后，如果它能够包含一些小区间，则从 set 里把这些小区间踢掉。答案就是这个 set 的大小。

3. 线段树
   类似并查集的思想，将每个点（其实是抽象的边）初始值设置为1，queries中每条路径通过线段树将i + 1 – j之间的所有点置0，线段树0 – n - 1的区间和即为距离长度。

代码

'''
Author: NEFU AB-IN
Date: 2024-08-09 22:27:53
FilePath: \LeetCode\3244\3244.py
LastEditTime: 2024-08-10 15:35:15
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class UnionFind:
        """Union-Find data structure."""

        def __init__(self, n: int):
            self.n = n
            self.comp_cnt = n  # Initially, each element is its own component
            self.parent = list(range(n))  # Parent pointers
            self.size = Arr.array(1, n)  # Size arrays for each node

        def find(self, p: int) -> int:
            """Find the root of the element p using non-recursive path compression."""
            rt = p
            while self.parent[rt] != rt:
                rt = self.parent[rt]
            while self.parent[p] != rt:
                self.parent[p], p = rt, self.parent[p]
            return rt

        def union(self, p: int, q: int) -> int:
            """Merge the set containing p into the set containing q."""
            rootP = self.find(p)
            rootQ = self.find(q)
            if rootP != rootQ:
                self.parent[rootP] = rootQ
                self.size[rootQ] += self.size[rootP]
                self.comp_cnt -= 1  # Decrease component count as two components are merged
            return rootQ

# ————————————————————— Division line ——————————————————————


class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        uf = Std.UnionFind(n - 1)
        ans = []

        for l, r in queries:
            l = uf.find(l)
            r = uf.find(r - 1)

            while l != r:
                uf.union(l, r)
                l = uf.find(l + 1)
            ans.append(uf.comp_cnt)
        return ans

from sortedcontainers import SortedSet
class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        st = SortedSet()  # Using SortedSet to maintain sorted order
        # Insert the initial intervals (i-1, i)
        for i in range(1, n):
            st.add((i - 1, i))

        ans = []
        for qry in queries:
            l, r = qry
            it = st.bisect_left((l, -1))
            if it < len(st) and st[it][0] == l and st[it][1] < r:
                # Remove all intervals [l', r') that are fully contained in [l, r)
                while it < len(st) and st[it][0] < r:
                    st.pop(it)
                st.add((l, r))
            ans.append(len(st))
        
        return ans

'''
Author: NEFU AB-IN
Date: 2024-08-10 16:30:03
FilePath: \LeetCode\3244\3244.1.py
LastEditTime: 2024-08-10 16:56:42
'''
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
# 3.8.19 import
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class SegTree:
        """
        https://github.com/boristown/leetcode/blob/main/SegTree.py
        A segment tree based on dynamic binary tree algorithm.
        Supports passing callback functions `f1` and `f2` to handle range queries (RMQ) such as range sum,
        range maximum, and range minimum.
        """

        def __init__(self, f1: Callable, f2: Callable, l: int, r: int, v: int = 0):
            """
            Initializes the segment tree [left, right).

            Example functions:
                Segment Sum:
                    f1 = lambda a, b: a + b
                    f2 = lambda a, n: a * n
                Segment Maximum:
                    f1 = lambda a, b: Math.max(a, b)
                    f2 = lambda a, n: a
                Segment Minimum:
                    f1 = lambda a, b: Math.min(a, b)
                    f2 = lambda a, n: a
            Args:
                f1: Function for combining segment values. (merge values from different intervals)
                f2: Function for applying values to segments. (Spread a value to an interval)
                l (int): Left boundary of the segment.
                r (int): Right boundary of the segment.
                v (int): Initial value for the segment.
            """
            self.default = v  # Default value for the segments
            self.ans = f2(v, r-l)  # Current result of the segment
            self.f1 = f1
            self.f2 = f2
            self.l = l  # left
            self.r = r  # right
            self.v = v  # init value
            self.lazy_tag = 0  # Lazy tag
            self.left = None  # SubTree(left, bottom)
            self.right = None  # SubTree(right, bottom)

        def __repr__(self) -> str:
            """Returns values of the segment."""
            anss = []
            for i in range(self.l, self.r):
                anss.append(str(self.query(i, i + 1)))
            return "seg: " + " ".join(anss)

        @property
        def mid_h(self) -> int:
            """Returns the midpoint of the segment."""
            return self.l + self.r >> 1

        def _create_subtrees(self) -> None:
            """Creates left and right subtrees if they do not exist."""
            midh = self.mid_h
            if not self.left and midh > self.l:
                self.left = Std.SegTree(self.f1, self.f2, self.l, midh, self.default)
            if not self.right:
                self.right = Std.SegTree(self.f1, self.f2, midh, self.r, self.default)

        def build(self, arr: List[int]) -> int:
            """
            Initializes the segment tree with values from arr.

            Args:
                arr: List of values to initialize the segment tree.

            Returns:
                The combined value of the segment tree.
            """
            m0 = arr[0]
            self.lazy_tag = 0
            if self.r == self.l + 1:
                self.v = m0
                self.ans = self.f2(m0, len(arr))
                return self.ans
            self.v = '#'
            midh = self.mid_h
            self._create_subtrees()
            self.ans = self.f1(self.left.build(arr[:midh - self.l]), self.right.build(arr[midh - self.l:]))
            return self.ans

        def cover_seg(self, l: int, r: int, v: int) -> int:
            """
            Covers the segment [left, right) with value v.

            Args:
                l (int): Left boundary of the cover range.
                r (int): Right boundary of the cover range.
                v: Value to cover the segment with.

            Returns:
                The combined value of the segment tree.
            """
            if self.v == v or l >= self.r or r <= self.l:
                return self.ans
            if l <= self.l and r >= self.r:
                self.v = v
                self.lazy_tag = 0
                self.ans = self.f2(v, self.r - self.l)
                return self.ans
            self._create_subtrees()
            if self.v != '#':
                self.left.v = self.v
                self.left.ans = self.f2(self.v, self.left.r - self.left.l)
                self.right.v = self.v
                self.right.ans = self.f2(self.v, self.right.r - self.right.l)
                self.v = '#'
            # push up
            self.ans = self.f1(self.left.cover_seg(l, r, v), self.right.cover_seg(l, r, v))
            return self.ans

        def inc_seg(self, l: int, r: int, v: int) -> int:
            """
            Increases the segment [left, right) by value v.

            Args:
                l (int): Left boundary of the increase range.
                r (int): Right boundary of the increase range.
                v: Value to increase the segment by.

            Returns:
                The combined value of the segment tree.
            """
            if v == 0 or l >= self.r or r <= self.l:
                return self.ans
            if l <= self.l and r >= self.r:
                if self.v == '#':
                    self.lazy_tag += v
                else:
                    self.v += v
                self.ans += self.f2(v, self.r - self.l)
                return self.ans
            self._create_subtrees()
            if self.v != '#':
                self.left.v = self.v
                self.left.ans = self.f2(self.v, self.left.r - self.left.l)
                self.right.v = self.v
                self.right.ans = self.f2(self.v, self.right.r - self.right.l)
                self.v = '#'
            self._pushdown()
            # push up
            self.ans = self.f1(self.left.inc_seg(l, r, v), self.right.inc_seg(l, r, v))
            return self.ans

        def inc_idx(self, idx: int, v: int) -> int:
            """
            Increases the value at index idx by value v.

            Args:
                idx (int): Index to increase.
                v: Value to increase by.

            Returns:
                The combined value of the segment tree.
            """
            if v == 0 or idx >= self.r or idx < self.l:
                return self.ans
            if idx == self.l == self.r - 1:
                self.v += v
                self.ans += self.f2(v, 1)
                return self.ans
            self._create_subtrees()
            if self.v != '#':
                self.left.v = self.v
                self.left.ans = self.f2(self.v, self.left.r - self.left.l)
                self.right.v = self.v
                self.right.ans = self.f2(self.v, self.right.r - self.right.l)
                self.v = '#'
            self._pushdown()
            # push up
            self.ans = self.f1(self.left.inc_idx(idx, v), self.right.inc_idx(idx, v))
            return self.ans

        def _pushdown(self) -> None:
            """Propagates the lazy tag to the child nodes."""
            if self.lazy_tag != 0:
                if self.left.v != '#':
                    self.left.v += self.lazy_tag
                else:
                    self.left.lazy_tag += self.lazy_tag
                self.left.ans += self.f2(self.lazy_tag, self.left.r - self.left.l)
                if self.right.v != '#':
                    self.right.v += self.lazy_tag
                else:
                    self.right.lazy_tag += self.lazy_tag
                self.right.ans += self.f2(self.lazy_tag, self.right.r - self.right.l)
                self.lazy_tag = 0

        def query(self, l: int, r: int) -> int:
            """
            Queries the range [left, right) for the combined value.

            Args:
                l (int): Left boundary of the query range.
                r (int): Right boundary of the query range.

            Returns:
                The combined value of the range.
            """
            if l >= r:
                return 0
            if l <= self.l and r >= self.r:
                return self.ans
            if self.v != '#':
                return self.f2(self.v, Math.min(self.r, r) - Math.max(self.l, l))  # the overlapping length
            self._create_subtrees()
            midh = self.mid_h
            self._pushdown()
            anss = []
            if l < midh:
                anss.append(self.left.query(l, r))
            if r > midh:
                anss.append(self.right.query(l, r))
            return reduce(self.f1, anss)

        @staticmethod
        def discretize(array):
            """Discretize the array and return the mapping dictionary. Index starts from 1"""
            sorted_unique = sorted(set(array))
            mapping = {val: idx + 1 for idx, val in enumerate(sorted_unique)}
            return [mapping[val] for val in array], mapping

# ————————————————————— Division line ——————————————————————


class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        def f1(a, b): return a + b
        def f2(a, n): return a * n
        sg = Std.SegTree(f1, f2, 0, n - 1, 1)
        ans = []
        for i, j in queries:
            sg.cover_seg(i + 1, j, 0)
            ans.append(sg.query(0, n))
        return ans