import math import sys input = sys.stdin.readline def init(node_number,start,end): global segement_tree,arr if start == end: segement_tree[node_number] = arr[start] return segement_tree[node_number] else: mid = (start+end)//2 segement_tree[node_number] = min(init(node_number*2, start, mid) , init(node_number*2+1, mid+1, end)) return segement_tree[node_number] def find_min_number(node_number,start,end,left,right): global segement_tree,INF if (left > end) or (right<start): return INF if (left <= start) and (end<=right): return segement_tree[node_number] mid = (start+end)//2 return min(find_min_number(node_number*2,start,mid,left,right), find_min_number(node_number*2+1,mid+1,end,left,right)) N,M = map(int,input().split()) INF = float('inf') segement_tree = [-1]*(N*4+20) arr = [int(input()) for _ in range(N)] init(1,0,N-1) for _ in range(M): left,right = map(int,input().split()) print(find_min_number(1,0,N-1,left-1,right-1))
2042 구간 합 구하기와 동일한 세그먼트 트리 문제였다
동일하지만 구간합을 저장 하는 것이 아닌 최소값을 저장하는 것이 달라진 점이다 그 외에는 동일하게 해주면 된다.
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ/백준] 1967 트리의 지름 (0) | 2021.04.08 |
---|---|
[BOJ/백준] 1806 부분합 (0) | 2021.04.08 |
[BOJ/백준] 2042 구간 합 구하기 (0) | 2021.03.12 |
[BOJ/백준] 2075 N번째 큰 수 (0) | 2021.03.12 |
[BOJ/백준] 2252 줄 세우기 (0) | 2021.03.12 |