백준/ Gold 1 문제 , 백준 파이썬 14428 , 수열과 쿼리 16 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 14428 , 수열과 쿼리 16 [세그먼트 트리]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
가장 작은 값을 찾으면서 그 값의 index를 효과적으로 찾아내기 위해서 2차원 배열을 이용한다.

 

문제 출처

https://www.acmicpc.net/problem/14428

14428번: 수열과 쿼리 16

 

 

 

참고

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-1-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-%ED%8C%8C%EC%9D%B4%EC%8D%AC-14438-%EC%88%98%EC%97%B4%EA%B3%BC-%EC%BF%BC%EB%A6%AC-17-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC

백준/ Gold 1 문제 , 백준 파이썬 14438 , 수열과 쿼리 17 [세그먼트 트리]

 

위 문제와 거의 동일.

 

 

 

 

 

 

풀이

 

 

1. 세그먼트 트리 생성 함수

 

이전 14438 문제와 풀이가 거의 동일하다. 

 

이 문제 또한 세그먼트 생성 함수 내에 min을 사용하여 tree에 각 자기 자식 노드들값중 최솟값을 부여한다.

 

 

 

2. 특정 노드 변경 함수

이 함수도 14438 문제 함수랑 동일하다.

 

min 을 활용하여 각 노드의 자식 노드들의 최솟값을 부여한다.

 

 

3. 최솟값을 찾는 함수

 

여기선 노드의 범위가 구간을 벗어나게 되면 return [sys.maxsize, sys.maxsize] 를 활용한다.

 

아무것도 담지 않고 리턴시키면 타입에러가 발생하니 주의하자.

 

이외의 풀이는 동일하다.

 

 

 

4. 입력 받기 및 각 함수들 호출

 

리스트는 값과 index를 담아 2차원으로 생성한다.

 

이후 update를 호출할때 해당 인덱스의 0번째값을 넣어서 호출하고

 

작은 값을 찾을 때는 결과값의 1번째 값 즉, 해당 값의 인덱스를 출력한다. 

 

 

 

정답

 

import sys
input=sys.stdin.readline

def init(start,end,index):
    if start==end:
        tree[index]=arr[start]
    else:
        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,w,v):
    if start>w or end<w:
        return 
    if start==end:
        tree[index]=v
        return
    mid=(start+end)//2
    update(start,mid,index*2,w,v)
    update(mid+1,end,index*2+1,w,v)
    tree[index]=min(tree[index*2],tree[index*2+1])
        
def find_min(start,end,index,left,right):
    if start>right or end<left:
        return [sys.maxsize,sys.maxsize]
    if start>=left and right>=end:
        return tree[index]
    mid=(start+end)//2
    return min(find_min(start,mid,index*2,left,right),find_min(mid+1,end,index*2+1,left,right))

N=int(input())
arr=[]
tmp=list(map(int,input().split()))
for i in range(N):
    arr.append([tmp[i],i+1])
tree=[0]*(N*4)

init(0,N-1,1)
for _ in range(int(input())):
    a,b,c=map(int,input().split())
    if a==1:
        arr[b-1][0]=c
        update(0,N-1,1,b-1,arr[b-1])
    elif a==2:
        print(find_min(0,N-1,1,b-1,c-1)[1])