[백준/BOJ] gold3 - 14427번 수열과 쿼리 15 (Python)

▶14427 - 수열과 쿼리 15

백준 로고

▶문제

길이가 N인 수열 A1, A2,..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러 개인 경우에는 인덱스가 작은 것을 출력한다.

수열의 인덱스는 1부터 시작한다.

 

 

▶입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2,..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

 

▶출력

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

728x90

▶풀이

최근 들어 세그먼트 트리에 관심이 생겨서 풀기 시작했다.

처음에는 세그먼트가 뭔지 몰라서 세그먼트 먼저 공부하고 문제를 풀었다.

 

세그먼트는 한번 익히면 골드 3부터 플래티넘까지 풀 수 있어서 좋은 것 같았다.

이번 문제는 update 부분은 거의 그대로 사용하면 됐다.

min index를 구하는 부분은 일부를 수정하면 되는 문제였다.

 

다음에 한번 세그먼트 트리를 다루는 포스팅을 해봐야겠다.

import sys
input = sys.stdin.readline

def init(start, end, index):
    if start > end:
        return
    
    if start == end:
        tree[index] = arr[start]
        return tree[index]
    
    mid = (start + end) // 2
    tree[index] = min(init(start, mid, index * 2), init(mid + 1, end, index * 2 + 1))

    return tree[index]


def update(start, end, index, what, value):
    if what < start or what > end:
        return 1000000000
    
    if start == end:   
        if start == what:
            tree[index] = value
            return value
        else:
            return tree[index]
    
    mid = (start + end) // 2
    if start <= what <= mid:
        tree[index] = min(tree[index * 2 + 1], update(start, mid, index * 2, what, value))
        return tree[index]
    elif mid <= what <= end:
        tree[index] = min(tree[index * 2], update(mid + 1, end, index * 2 + 1, what, value))
        return tree[index]


def get_min(start, end, index, value):
    global result

    if tree[index] == 0 or tree[index] != value or result != 0:
        return
    
    if start == end and tree[index] == value:
        result = start
        return
    
    mid = (start + end) // 2
    get_min(start, mid, index * 2, value)
    get_min(mid + 1, end, index * 2 + 1, value)
    


n = int(input())
answer = []
arr = list(map(int, input().split()))

tree = [0 for _ in range(len(arr) * 4)]
init(0, len(arr) - 1, 1)

m = int(input())

for i in range(m):
    li = list(map(int, input().split()))

    if li[0] == 1:
        update(0, len(arr) - 1, 1, li[1] - 1, li[2])
    else:
        result = 0
        get_min(0, len(arr) - 1, 1, tree[1])
        answer.append(result + 1)

for ans in answer:
    print(ans)