백준/ Platinum 4 문제 , 백준 파이썬 17408 , 수열과 쿼리 24 [세그먼트 트리]

백준/ Platinum 4 문제 , 백준 파이썬 17408 , 수열과 쿼리 24 [세그먼트 트리]

 

 

풀이 시간

 

 

 

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

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

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

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

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

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

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


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


<덧붙일 말>
오류 잡는데 2시간은 쓴 것 같다.
아무리봐도 틀린게 없는데, 예제도 다틀리는게 아니고 어떤 부분에서만 틀려서 대체 어디가 틀린건지 도무지 몰랐었다.
그러다가 우연히 입력을 막 해보던 도중 같은 값을 집어 넣었는데 넣을때마다 값이 바뀌는걸 알게 되었고 알고보니 getMax 함수 내에서 tree를 변경하지말고 값만 추출했어야했는데 tree에 할당을 해버리는 코드 한줄이 있었다. 그 부분때문에 무려 2시간을 잡아먹음.... 그래도 우연찮게라도 찾아서 다행이다.
덕분에 코드 로직을 몇번이고 파헤쳐보고 뜯어보면서 더 잘 이해한 문제이다.

 

 

문제 출처

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

17408번: 수열과 쿼리 24

 

 

참고

https://newdeal123.tistory.com/22

[BOJ][백준]세그먼트 트리-17408번 수열과 쿼리 24

 

 

 

 

 

풀이

 

 

 

1.  세그먼트 트리 생성 

 

리프 노드에 배열의 값과 위치를 두개 저장시킨다.

 

이후 부모노드로 올라가면서 자식노드들과 비교하여 더 높은 값을 가지고 있는 노드를 부모노드에 저장한다.

 

 

 

 

2. 특정 부분 교체 함수

 

리프노드에는 바꿀 값과 바꿀 위치를 저장하고

 

다시 부모노드들을 새로 세팅해준다.

 

 

 

3. 구간내 최대값 찾는 함수

 

이 getMax 함수를 통해서 자식 노드들의 첫번째 값에 저장된 값을 서로 비교하여 가장 큰값이 그 구간내에서 가장 큰 값이다. 이 값을 가진 노드를 리턴시키면된다.

 

 

 

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

 

구간내 가장 큰 값을 찾는다는 것은 첫번째로 큰값과 두번째로 큰값을 더한다는 얘기이다.

 

 

그렇다면 우선 첫번째로 큰값을 구해보자.

 

그 값이 b~c 구간내에서 가장 큰 값이고 이 값이 담긴 노드를 result 에 할당한다.

 

이제 이 result 1번 인덱스에는 그 가장 큰 값이 배열에 몇번째 위치에 담겨있는지 값이 매겨져있다.

 

그렇다면, 두번째로 큰값은 이 첫번째로 큰 값을 기준으로 왼쪽에 있던가 오른쪽에 있던가 할 것이다.

 

이 값을 찾기위해 각 getMax 함수를 첫번째로 큰값의 위치를 기준으로 b ~ 위치값 -1 | 위치값+1~c 로

 

나누어서 찾는것이다.

 

그렇다면 각 결과 값은 각각의 구간내에서 가장 큰값을 리턴할 것이고, 이중에서도 가장 큰값이 바로 b~c 구간내에서 두번째로 큰값이다.

 

이 두 값을 더해주면 원하는 값이 출력된다.

 

 

 

정답

 

 

 

import sys
input=sys.stdin.readline

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

def update(start,end,index,w,v):
    if w<start or w>end:
        return tree[index]
    if start==end:
        tree[index]=[v,w]
        return tree[index]
    mid=(start+end)//2
    left_node=update(start,mid,index*2,w,v)
    right_node=update(mid+1,end,index*2+1,w,v)
    if left_node[0]>right_node[0]:
        tree[index]=left_node
    else:
        tree[index]=right_node
    return tree[index]
    
def getMax(start,end,index,left,right):
    if start>right or end < left:
        return [0,0]
    if start>=left and right>=end:
        return tree[index]
    mid=(start+end)//2
    left_node=getMax(start,mid,index*2,left,right)
    right_node=getMax(mid+1,end,index*2+1,left,right)
    if left_node[0]>right_node[0]:
        return left_node
    else:
        return right_node


N=int(input())
arr=list(map(int,input().rstrip().split()))
arr=[0]+arr
tree=[[0,0] for _ in range(N*4)]

init(1,N,1)

M=int(input())
for i in range(M):
    a,b,c=map(int,input().split())
    if a==1:
        arr[b]=c
        update(1,N,1,b,c)
    elif a==2:
        result=getMax(1,N,1,b,c)
        left_MAX=getMax(1,N,1,b,result[1]-1)
        right_MAX=getMax(1,N,1,result[1]+1,c)
        print(result[0]+max(left_MAX[0],right_MAX[0]))