14427. 수열과 쿼리 15

업데이트 시간 : 2023-07-17 13:29:10 +0000

[Gold III] 수열과 쿼리 15 - 14427

문제 링크

성능 요약

메모리: 219532 KB, 시간: 1248 ms

분류

자료 구조, 우선순위 큐, 세그먼트 트리

문제 설명

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

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

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

입력

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

둘째 줄에는 A₁, A₂, ..., A_N이 주어진다. (1 ≤ A_i ≤ 10⁹)

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

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

출력

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

💡 Solutions

📄 수열과 쿼리 15.py

import sys
N = int(sys.stdin.readline())
As = [0]+ list(map(int,sys.stdin.readline().split()))
M = int(sys.stdin.readline())
Qs = [list(map(int,sys.stdin.readline().split())) for _ in range(M)]


segment_tree = [[0, 0] for _ in range(4*N+1)]


def tree(start, end, index):
    # start와 end가 같으면 리프노드
    if start == end :
        segment_tree[index] = [As[start], start]
    else:
        mid = (start+end) // 2
        left = index*2
        right = index*2+1
        tree(start, mid, left)   # 좌측으로
        tree(mid+1, end, right) # 우측으로
        
        small = left
        if segment_tree[left][0] > segment_tree[right][0]:
            small = right
        
        segment_tree[index] = [segment_tree[small][0], segment_tree[small][1]]


# 3. 트리 값 바꿔주기
def update(start, end, index, update_idx, update_data):
	# update 하려는 범위가 초과될 경우// (start,end) 범위에 없을 경우
    if start > update_idx or end < update_idx:
        return
    
    # 리프노드까지 바꿔주었으면 재귀함수를 끝낸다.
    if start == end:
        segment_tree[index] = [update_data, update_idx]
        return

	# update_idx가 관여하고 있는 노드들을 찾아서 바꿔준다.
    mid = (start + end) // 2
    left = index*2
    right = index*2+1
    # 다음 노드로 찾아간다.
    update(start, mid, index*2, update_idx, update_data)
    update(mid+1, end, index*2+1, update_idx, update_data)
    
    small = left
    if segment_tree[left][0] > segment_tree[right][0]:
        small = right
    
    segment_tree[index] = [segment_tree[small][0], segment_tree[small][1]]

tree(1, N, 1)
for Q in Qs:
    q, *items = Q

    if q == 1:
        update(1, N, 1, items[0], items[1])
    else:
        print(segment_tree[1][1])