(백준 14428 수열과 쿼리 16

• tags : (algorithm

  No matching post could be found

  - (segment tree
• 문제 링크 : https://www.acmicpc.net/problem/14428
• 풀이 링크
  • Python

• 전형적인 세그먼트 트리 문제
• 각 구간별 최솟값의 인덱스를 저장하고, 쿼리의 구간의 최솟값 인덱스를 출력
  • 최솟값이 여러개인 경우, 가장 작은 인덱스를 출력

def init(self) -> None:
    self.find_idx(1, 1, self.N)
    for idx, x in enumerate(self.idx):
        self.tree[x] = idx
    self.init_tree()

def find_idx(self, node: int, left: int, right: int) -> None:
    if left >= right:
        self.idx[left] = node
        return
    mid = (left + right) // 2
    self.find_idx(node * 2, left, mid)
    self.find_idx(node * 2 + 1, mid + 1, right)

def init_tree(self) -> None:
    for i in range(len(self.tree) - 1, 0, -1):
        if i * 2 + 1 > len(self.tree):
            continue
        left = self.seq[self.tree[i * 2]]
        right = self.seq[self.tree[i * 2 + 1]]
        if not left * right:
            continue
        if left <= right:
            self.tree[i] = self.tree[i * 2]
        else:
            self.tree[i] = self.tree[i * 2 + 1]

• 세그먼트 트리 초기화
• init()메서드를 사용하여 초기화하고, find_idx(), init_tree()메서드 호출
  • find_idx()는 세그먼트 트리와 수열의 인덱스를 저장하여 더욱 빠르게 작동할 수 있도록 함
  • init_tree()를 사용하여 세그먼트 트리 초기화
• 초기화할 때, 값을 찾을 때, 갱신할 때 최솟값이 여러개이면 가장 작은 인덱스를 가져오는 부분을 주의하여 작성