백준 14427 : 수열과 쿼리 15 (Python)

본문 링크

import sys
input=sys.stdin.readline

def init(node , start , end):

    if start==end:
        tree[node]=[ L[start][0] , L[start][1] ]
        return

    init(node*2 , start , (start+end)//2)
    init(node*2+1 , (start+end)//2+1 , end)

    if tree[node*2][0]<tree[node*2+1][0]:
        tree[node]=[ tree[node*2][0] , tree[node*2][1] ]
    elif tree[node*2][0]>tree[node*2+1][0]:
        tree[node]=[ tree[node*2+1][0] , tree[node*2+1][1] ]
    else:
        if tree[node*2][1] <= tree[node*2+1][1]:
            tree[node] = [tree[node * 2][0], tree[node * 2][1]]
        else:
            tree[node] = [tree[node * 2 + 1][0], tree[node * 2 + 1][1]]


def update(node , start , end , index , value):

    if index<start or index>end:
        return

    if start==end:
        tree[node]=[value,index]
        return

    update(node*2 , start , (start+end)//2 , index , value)
    update(node*2+1 , (start+end)//2+1 , end , index , value)

    if tree[node*2][0]<tree[node*2+1][0]:
        tree[node]=[ tree[node*2][0] , tree[node*2][1] ]
    elif tree[node*2][0]>tree[node*2+1][0]:
        tree[node]=[ tree[node*2+1][0] , tree[node*2+1][1] ]
    else:
        if tree[node*2][1] <= tree[node*2+1][1]:
            tree[node] = [tree[node * 2][0], tree[node * 2][1]]
        else:
            tree[node] = [tree[node * 2 + 1][0], tree[node * 2 + 1][1]]


def query( node , start , end , left ,right):

    if left>end or right<start:
        return [int(1e9) ,int(1e9)]

    if left<=start and right>=end: #포함한다면
        return tree[node]

    leftmin=query(node*2 ,start , (start+end)//2 , left , right)
    rightmin=query(node*2+1 , (start+end)//2+1 , end, left , right)

    if leftmin[0]<rightmin[0]:
        return leftmin
    elif leftmin[0]>rightmin[0]:
        return rightmin
    elif leftmin[0]==rightmin[0]:

        if leftmin[1] <= rightmin[1]:
            return leftmin
        elif leftmin[1] > rightmin[1]:
            return rightmin



N=int(input())
tree=[0]*(4*N)
L=list(map(int,input().split()))
for i in range(len(L)):
    L[i]=[L[i],i]

init(1,0,N-1)

for i in range(int(input())):

    Q=list(map(int,input().split()))

    if Q[0]==1:
        update(1,0,N-1,Q[1]-1 , Q[2] )
    else:
        Answer=query(1,0,N-1 , 0 , N-1)
        print(Answer[1]+1)

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용해서 풀었습니다.
수열과 쿼리 16 문제와 아주 비슷하기 때문에 코드를 살짝만 수정했습니다.

두번째 쿼리인 특정 범위의 가장작은 값의 인덱스를 구하는 것인데 이 문제는 모든 배열에서의 가장 작은값의 인덱스를 구해야합니다.

따라서 입력을 살짝 바꾸어 주고 query 함수의 호출 범위를 매번 리스트 인덱스 전체로 잡았습니다.

자세한 내용은 수열과 쿼리 16 - Python 이 글에 정리했습니다.