[백준] 2357번 - 최솟값과 최댓값 (파이썬)

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

# 최솟값과 최댓값
import sys
input = sys.stdin.readline
MAX = sys.maxsize

N, M = map(int, input().split())
arr = [0]
for _ in range(N):
    arr.append(int(input()))
tree = [[MAX, 0] for _ in range(N+1)]
tree2 = [[MAX, 0] for _ in range(N+1)]


def update(i, target):
    while i <= N:
        tree[i][0] = min(tree[i][0], target)
        tree[i][1] = max(tree[i][1], target)
        i += (i & -i)


def update2(i, target):
    while i > 0:
        tree2[i][0] = min(tree2[i][0], target)
        tree2[i][1] = max(tree2[i][1], target)
        i -= (i & -i)


def find(start, end):
    result_min = MAX
    result_max = 0
    prev = start
    curr = prev + (prev & -prev)
    while curr <= end:
        result_min = min(result_min, tree2[prev][0])
        result_max = max(result_max, tree2[prev][1])
        prev = curr
        curr = prev + (prev & -prev)
    result_min = min(result_min, arr[prev])
    result_max = max(result_max, arr[prev])

    prev = end
    curr = prev - (prev & -prev)
    while curr >= start:
        result_min = min(result_min, tree[prev][0])
        result_max = max(result_max, tree[prev][1])
        prev = curr
        curr = prev - (prev & -prev)

    print(result_min, result_max)


for i, x in enumerate(arr):
    if i > 0:
        update(i, x)
        update2(i, x)

for _ in range(M):
    start, end = map(int, input().split())
    find(start, end)

 

자료구조, 펜윅트리

1. 입력을 받고 트리를 두 가지를 할당해준다.

2. 초기값을 이용해서 펜윅트리를 업데이트해준다. 2차원배열로 트리를 만들어준다 0 = 쵯솟값, 1 = 최댓값

    - update : 앞에서 뒤로 펜윅트리를 만든다.

    - update2 : 뒤에서 앞으로 펜윅트리를 만든다.

3. 구해야 할 구간을 입력받으면서 해당 구간에서의 최솟값과 최댓값을 찾아서 return (find 함수)

    - tree2는 start부터 end전까지 최솟값, 최댓값을 업데이트 인덱스를 앞으로 이동

    - 중간의 arr값을 참고해서 한 번 더 비교해준다

    - tree는 end부터 start전까지 최솟값,최댓값을 업데이트 인덱스를 뒤로 이동

4. 출력

 

백준 10868번 - 최솟값 : https://2hs-rti.tistory.com/90

[백준] 10868번 - 최솟값 (파이썬)

기존 최솟값 문제에서 변형해서 최댓값도 다룬 문제이다.