[Python] 백준 14427번: 수열과 쿼리 15

https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

 

 > 접근

세그먼트 트리의 노드 형식을 [VALUE, INDEX]으로 맞추고 초기화 함수, 업데이트 함수만 구현해주면 된다. 어차피 전체 범위에 대해서만 쿼리를 하므로 쿼리 함수는 따로 구현하지 않고 seg_tree[1]를 참조하기만 해도 된다.

 

 + 제목을 보고 무작정 세그먼트 트리로 풀 생각만 했었는데, 전체 범위에서 가장 작은 값을 찾는 것이므로 우선순위큐를 이용하여 간단하게 풀 수도 있다.

 

import sys
input = sys.stdin.readline
VALUE, INDEX = 0, 1

def initialize_seg_tree(index, left, right):
  if(left == right):
    seg_tree[index] = [nums[left],left]     
  else:
    mid = (left + right) // 2
    initialize_seg_tree(index*2, left, mid)
    initialize_seg_tree(index*2+1, mid+1, right)

    smaller_index = index*2
    if(seg_tree[index*2][VALUE] > seg_tree[index*2+1][VALUE]):
      smaller_index = index*2+1

    seg_tree[index] = [seg_tree[smaller_index][VALUE],seg_tree[smaller_index][INDEX]]   

def update_seg_tree(index, left, right, start, end, value):
  if(right < start or end < left):
    return
  if(left == right):
    seg_tree[index] = [value, left]
    return

  mid = (left + right) // 2
  update_seg_tree(index*2, left, mid, start, end, value)
  update_seg_tree(index*2+1, mid+1, right, start, end, value)

  smaller_index = index*2     
  if(seg_tree[index*2][VALUE] > seg_tree[index*2+1][VALUE]):
    smaller_index = index*2+1
                            
  seg_tree[index] = [seg_tree[smaller_index][VALUE],seg_tree[smaller_index][INDEX]] 


if __name__ == '__main__':
  N = int(input())
  nums = [0] + list(map(int, input().split()))

  seg_tree = [[0,0]]*(4*N) # value, index
  initialize_seg_tree(1, 1, N)      

  M = int(input())
  for _ in range(M):
    order = list(map(int, input().split()))
    if(order[0] == 1):
      update_seg_tree(1, 1, N, order[1], order[1], order[2])
    else:
      print(seg_tree[1][INDEX])