[백준/세그먼테이션 트리] 10868번 최솟값

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

10868번: 최솟값

 

 

 

직전에 풀었던 최솟값 과 최댓값 구하기와 같았다.

2022.03.15 - [알고리즘 공부] - [백준/세그먼테이션 트리] 2357 최솟값과 최댓값

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

import sys
from math import *

def init(node,start,end):
    if start == end:
        tree[node] = arr[start]
        return tree[node]

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

def find(node,start,end,left,right):
    if start>right or end < left:
        return 1000000001

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

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

input =sys.stdin.readline
n,m = map(int,input().split())
arr = [int(input()) for _ in range(n)]

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

tree = [0] * t_size

init(1,0,n-1)

for _ in range(m):
    a,b = map(int,input().split())
    print(find(1,0,n-1,a-1,b-1))