[백준 14428번] 수열과 쿼리 16 (Python3)

import sys
input = sys.stdin.readline

N = int(input())

data = [*map(int,input().split())]

segtree = {}
def makeseg(start,end,x):
  if start == end:
    segtree[x] = start
  else:
    mid = (start+end)//2
    seg1 = makeseg(start,mid,x*2)
    seg2 = makeseg(mid+1,end,x*2+1)
    if data[seg1] < data[seg2]:
      segtree[x] = seg1
    elif data[seg2] < data[seg1]:
      segtree[x] = seg2
    else:
      segtree[x] = min(seg1,seg2)
  return segtree[x]

def editseg(i,start,end,x):
  if start == end == i:
    return i
  mid = (start+end)//2
  if i <= mid:
    seg = editseg(i,start,mid,x*2)
    if data[seg] < data[segtree[x*2+1]]:
      segtree[x] = seg
    elif data[seg] == data[segtree[x*2+1]]:
      segtree[x] = min(segtree[x*2+1],seg)
    else:
      segtree[x] = segtree[x*2+1]
  else:
    seg = editseg(i,mid+1,end,x*2+1)
    if data[seg] < data[segtree[x*2]]:
      segtree[x] = seg
    elif data[seg] == data[segtree[x*2]]:
      segtree[x] = min(segtree[x*2],seg)
    else:
      segtree[x] = segtree[x*2]
  return segtree[x]

def minseg(i,j,start,end,x):
  if start == i and end == j:
    return segtree[x]
  mid = (start+end)//2
  if j <= mid:
    return minseg(i,j,start,mid,x*2)
  if i > mid:
    return minseg(i,j,mid+1,end,x*2+1)
  seg1 = minseg(i,mid,start,mid,x*2)
  seg2 = minseg(mid+1,j,mid+1,end,x*2+1)
  if data[seg1] < data[seg2]:
    return seg1
  if data[seg1] > data[seg2]:
    return seg2
  return min(seg1,seg2)

makeseg(0,N-1,1)

M = int(input())
for i in range(M):
  q,i,j = map(int,input().split())
  if q == 1:
    data[i-1] = j
    editseg(i-1,0,N-1,1)
  else:
    print(minseg(i-1,j-1,0,N-1,1)+1)

 

또 전형적인 세그먼트 트리 문제이다.

이전에 풀었던 문제와는 약간 다른게 출력해야하는 데이터가 값이 아니라 인덱스이다.

이거때문에 세그먼트 트리 데이터를 인덱스값으로 설정해서 풀었는데, 푸는 중간에 깨달았다. 그냥 값을 기준으로 할걸...

 

그냥 값에 대해서 세그먼트 트리 만들고 값의 인덱스는 따로 dict로 저장했으면 훨씬 편했을걸, 세그먼트 값을 인덱스로 하다보니까 조건문 만들기가 까다로웠다.

 

 

오늘의 교훈) 세그먼트 트리는 왠만하면 값을 기준으로 만들자