백준 14428 : 수열과 쿼리 16 (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,A,B=map(int,input().split())
    if Q==1:
        update(1,0,N-1,A-1 , B)
    else:
        Answer=query(1,0,N-1 , A-1 , B-1)
        print(Answer[1]+1)

📌 어떻게 접근할 것인가?

세그먼트 트리를 이용해 풀었습니다.

쿼리는 2개 입니다. 값을 변경하는 것과 특정 구간에서 가장 값이 작은 수의 인덱스를 구하라.

따라서 세그먼트 트리를 2차원 배열로 만들었습니다.

배열에 배열의 값과 인덱스 값을 넣었으며 배열의 값에 따라서 값을 더 작은쪽을 저장했습니다.

이때 중요한 것은 배열의 값이 같으면 인덱스 값이 더 작은 쪽을 반환해야합니다.

그리고 인덱스는 0부터 시작했기 때문에 쿼리에서 주어지는 변수를 인덱스로 사용할때 -1 을 해줘야 합니다.