[세그먼트 트리/파이썬] 백준 2357번: 최솟값과 최댓값 / 골드 1

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

2357번: 최솟값과 최댓값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100

www.acmicpc.net

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = []
for _ in range(n):
    nums.append(int(input()))

s_tree = [[0 for _ in range(2)] for _ in range(4*n)]

def merge(left, right):
    min_val = min(left[0], right[0])
    max_val = max(left[1], right[1])
    return [min_val, max_val]

def build(node, left, right):
    if left == right:  # leaf node
        s_tree[node] = [nums[left], nums[left]]
        return s_tree[node]

    mid = left + (right - left)//2
    a = build(2*node, left, mid)
    b = build(2*node+1, mid+1, right)
    s_tree[node] = merge(a, b)
    return s_tree[node]

def query(start, end, node, left, right):
    if end < left or right < start:
        return [9876543210, -9876543210]

    if start <= left and right <= end:
        return s_tree[node]

    mid = left + (right - left)//2
    a = query(start, end, 2*node, left, mid)
    b = query(start, end, 2*node+1, mid+1, right)
    return merge(a, b)


build(1, 0, n-1)
for _ in range(m):
    start, end = map(int, input().split())
    result = query(start-1, end-1, 1, 0, n-1)
    print(*result)

세그먼트 트리로 그냥 풀리는 문제!