Leetcode 3161. Block Placement Queries

문제

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.

You are given a 2D array queries, which contains two types of queries:

For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.
Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.

양의 x축 방향으로 무한히 뻗어 있는 수직선이 있으며, 원점은 0입니다.

두 종류의 쿼리를 포함하는 2차원 배열 queries가 주어집니다.

1. queries[i] = [1, x]

   • 원점으로부터 거리 x인 위치에 장애물을 설치합니다.
   • 이 쿼리가 주어질 때 위치 x에는 장애물이 존재하지 않는 것이 보장됩니다.

2. queries[i] = [2, x, sz]

   • 구간 [0, x]의 어딘가에 크기가 sz인 블록을 놓을 수 있는지 확인합니다.
   • 블록 전체가 반드시 [0, x] 범위 안에 있어야 합니다.
   • 블록이 장애물과 겹치면 놓을 수 없습니다.
   • 단, 블록이 장애물에 닿는 것은 허용됩니다.
   • 실제로 블록을 놓는 것은 아니며, 각 쿼리는 서로 독립적입니다.

각 2번 쿼리에 대한 결과를 담은 불리언 배열 results를 반환하세요.

results[i]는 해당 2번 쿼리에서 지정된 블록을 놓을 수 있다면 true, 그렇지 않다면 false입니다.

---

예시

입력:
queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

출력:
[false, true, true]

설명:

• query 0 = [1, 2]

  • x = 2 위치에 장애물을 설치합니다.

이제 수직선은 대략 다음과 같습니다.

0 -------- 2 -------- 3
           ▲
         장애물

• query 1 = [2, 3, 3]

  • [0, 3] 구간 안에 길이 3인 블록을 놓을 수 있는지 확인합니다.
  • 장애물이 x = 2에 있기 때문에 연속해서 사용할 수 있는 최대 공간은 길이 2입니다.
  • 따라서 길이 3인 블록은 놓을 수 없습니다.
  • 결과: false

• query 2 = [2, 3, 1]

  • [0, 3] 안에 길이 1인 블록을 놓을 수 있습니다.
  • 결과: true

• query 3 = [2, 2, 2]

  • [0, 2] 구간에 길이 2인 블록을 놓을 수 있습니다.
  • 블록의 끝이 x = 2의 장애물에 닿는 것은 허용되므로 [0, 2]에 배치할 수 있습니다.
  • 결과: true

따라서 최종 결과는

[false, true, true]

입니다.

---

제한

• $1 \le \text{queries.length} \le 15 \times 10^4$
• $2 \le \text{queries}[i].\text{length} \le 3$
• $1 \le \text{queries}[i][0] \le 2$
• $1 \le x,\ sz \le \min(5 \times 10^4,\ 3 \times \text{queries.length})$
• 입력은 1번 쿼리가 주어질 때, 거리 $x$인 위치에 기존 장애물이 없도록 생성됩니다.
• 입력에는 최소 하나 이상의 2번 쿼리가 존재하도록 생성됩니다.

---

풀이

해당 문제는 세그먼트 트리에 어떤 값을 저장할 것인지가 가장 중요하다.

각 장애물의 위치를 index라고 할 때, 세그먼트 트리의 리프 노드 tree[index]에는

index 위치의 장애물과 바로 왼쪽에 있는 장애물 사이의 거리

를 저장한다.

예를 들어 장애물이 다음과 같이 존재한다고 하자.

0 ---- 4 ------ 10

그러면

tree[4] = 4 - 0 = 4
tree[10] = 10 - 4 = 6

이 된다.

그리고 세그먼트 트리의 각 구간에는 이 값들의 최댓값을 저장한다.

따라서 특정 위치까지의 구간을 세그먼트 트리에서 조회하면, 그 구간 안에 완전히 포함되는 빈 공간 중 가장 긴 길이를 빠르게 구할 수 있다.

문제는 새로운 장애물이 추가되었을 때이다.

새로운 장애물 x가 추가되면 x의 바로 왼쪽 장애물뿐만 아니라 바로 오른쪽 장애물의 값도 변경된다.

예를 들어

0 ---------- 10

에서 4에 새로운 장애물이 추가되면 기존의

tree[10] = 10

은

tree[4] = 4
tree[10] = 6

으로 변경되어야 한다.

따라서 현재 존재하는 장애물들의 위치를 정렬된 상태로 관리하면서, 새로운 장애물의 바로 왼쪽과 오른쪽 장애물을 빠르게 찾을 필요가 있다.

이를 위해 SortedList를 사용한다.

장애물 x를 추가할 때 SortedList에서 이분 탐색을 통해

prev < x < next

를 만족하는 가장 가까운 prev, next를 찾는다.

이후 세그먼트 트리를 다음과 같이 갱신한다.

tree[x]    = x - prev
tree[next] = next - x

따라서 장애물 추가는 SortedList 탐색과 세그먼트 트리 갱신을 포함하여 $O(\log N)$ 에 처리할 수 있다.

두 번째 쿼리 [2, x, size]에서는 먼저 x 이하에서 가장 오른쪽에 있는 장애물 prev를 찾는다.

이때 가능한 공간은 두 종류로 나눌 수 있다.

1. prev 이전에서 두 장애물 사이에 완전히 존재하는 공간
2. 마지막 장애물 prev부터 쿼리의 끝인 x까지의 공간

첫 번째 경우는 세그먼트 트리에서

segment.query(0, prev)

를 통해 가장 긴 공간을 구할 수 있다.

두 번째 경우의 길이는 단순히

x - prev

이다.

따라서 실제로 사용할 수 있는 가장 긴 공간은

max(segment.query(0, prev), x - prev)

이고, 이 값이 size 이상이라면 블록을 배치할 수 있다.

결과적으로 장애물 추가와 블록 배치 가능 여부 확인을 모두 $O(\log N)$ 에 처리할 수 있다.

class SegTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size * 4 + 1)

    def _update(self, seg_left: int, seg_right: int, node_index: int, index: int, value: int):
        if seg_left == seg_right:
            self.tree[node_index] = value
            return

        mid = (seg_left + seg_right) // 2

        if index <= mid:
            self._update(seg_left, mid, node_index * 2, index, value)
        else:
            self._update(mid + 1, seg_right, node_index * 2 + 1, index, value)

        self.tree[node_index] = max(self.tree[node_index * 2], self.tree[node_index * 2 + 1])

    def update(self, index: int, value: int):
        self._update(0, self.size - 1, 1, index, value)

    def _query(self, qur_left: int, qur_right: int, seg_left: int, seg_right: int, node_index: int) -> int:
        if qur_left <= seg_left <= seg_right <= qur_right:
            return self.tree[node_index]

        if qur_left > seg_right or qur_right < seg_left:
            return 0

        mid = (seg_left + seg_right) // 2
        ans = 0

        if mid >= qur_left:
            ans = max(ans, self._query(qur_left, qur_right, seg_left, mid, node_index * 2))
        
        if mid < qur_right:
            ans = max(ans, self._query(qur_left, qur_right, mid + 1, seg_right, node_index * 2 + 1))

        return ans

    def query(self, left: int, right: int) -> int:
        return self._query(left, right, 0, self.size - 1, 1)

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        SIZE = 5 * 10 ** 4 + 1
        segment = SegTree(SIZE)
        positions = SortedList([0, SIZE])
        segment.update(SIZE, SIZE)

        ans = []

        for query in queries:
            if query[0] == 1:
                _, x = query
                index = positions.bisect(x)
                prev = index - 1

                segment.update(x, x - positions[prev])
                segment.update(positions[index], positions[index] - x)

                positions.add(x)
            else:
                _, x, size = query
                index = positions.bisect(x)
                prev = index - 1

                largest = segment.query(0, positions[prev])
                left = x - positions[prev]

                ans.append(max(largest, left) >= size)

        return ans