[백준/세그먼테이션 트리] 2357 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

처음에는 list를 잘라서 min, max를 구했는데 시간초과가 떴다.

import sys

input = sys.stdin.readline

N,M = map(int,input().split())

arr = [int(input()) for _ in range(N)]

for _ in range(M):
    a,b = map(int,input().split())

    print(min(arr[a-1:b]),max(arr[a-1:b]))

 

 

트리를 최솟값, 최댓값을 따로 만든다.

 

풀이 방법은 세그멘테이션 트리의 코드와 같음.

 

import sys
from math import *

input = sys.stdin.readline

def initMin(node,start,end):
    if start == end:
        treeMin[node] = arr[start]
        return treeMin[node]

    mid = (start+end)//2
    treeMin[node] = min(initMin(node*2,start,mid),initMin(node*2+1,mid+1,end))
    return treeMin[node]

def initMax(node,start,end):
    if start == end:
        treeMax[node] = arr[start]
        return treeMax[node]

    mid = (start+end)//2
    treeMax[node] = max(initMax(node*2,start,mid),initMax(node*2+1,mid+1,end))
    return treeMax[node]

#최소 구하기
def findMin(node,start,end,left,right):
    if start > right or end < left:
        return 1000000001
    
    if left<=start and end <= right:
        return treeMin[node]

    mid = (start+end)//2
    return min(findMin(node*2,start,mid,left,right),findMin(node*2+1,mid+1,end,left,right))

def findMax(node,start,end,left,right):
    if start > right or end < left:
        return 0
    if left<=start and end <= right:
        return treeMax[node]

    mid = (start+end)//2
    return max(findMax(node*2,start,mid,left,right),findMax(node*2+1,mid+1,end,left,right))


N,M = map(int,input().split())

arr = [int(input()) for _ in range(N)]

h = int(ceil(log2(N)))
t_size = 1<<(h+1)

treeMax = [0] * t_size
treeMin = [0] * t_size
#세그멘트 트리만들기
initMin(1,0,N-1)
initMax(1,0,N-1)

for _ in range(M):
    a,b = map(int,input().split())

    print(f'{findMin(1,0,N-1,a-1,b-1)} {findMax(1,0,N-1,a-1,b-1)}')