[백준] 2357번: 최솟값과 최댓값

문제

백준 - 2357번: 최솟값과 최댓값

분석

M개의 주어진 구간에서의 최솟값과 최댓값을 구하는 문제이다.

지난번에 배운 세그먼트 트리에서 응용하면 된다.
구간합을 넣는 대신, 최소 최대를 넣으면 된다.
메소드를 여러개 많들기 보다 tree의 한 노드에 최소, 최대를 모두 넣어 한 번에 계산하였다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

import math
n, m = map(int, input().split())
h = math.ceil(math.log2(n))
INF = sys.maxsize
tree = [[INF, -INF]] * (1 << (h + 1))
arr = [0]

def segment(node, s, e):
    if s == e:
        tree[node] = [arr[s], arr[s]]
        return
    segment(node*2, s, (s+e)//2)
    segment(node*2+1, (s+e)//2+1, e)
    left_min, left_max = tree[node*2]
    right_min, right_max = tree[node*2+1]
    mn = min(left_min, right_min)
    mx = max(left_max, right_max)
    tree[node] = [mn, mx]

def get(node, s, e, l, r):
    if s > r or e < l:
        return [INF, -INF]
    if l <= s and e <= r:
        return tree[node]
    left = get(node*2, s, (s+e)//2, l, r)
    right = get(node*2+1, (s+e)//2+1, e, l, r)
    return [min(left[0], right[0]), max(left[1], right[1])]

for _ in range(n):
    arr.append(int(input()))
segment(1, 1, n)
for _ in range(m):
    a, b = map(int, input().split())
    print(*get(1, 1, n, a, b))

끝으로..

지난번에 학습한 세그먼트 트리에서 살짝 응용한 문제였다. 복습할 수 있는 문제를 풀어 좋았다.