# BOJ - 2357 - 최솟값과 최댓값

Updated:

``````import sys, math

def initMaxSegmentTree(arr, segmentTree, node, left, right):
if left == right:
segmentTree[node] = arr[left]
else:
mid = (left + right) // 2
segmentTree[node] = max(initMaxSegmentTree(arr, segmentTree, node * 2, left, mid), initMaxSegmentTree(arr, segmentTree, node * 2 + 1, mid + 1, right))
return segmentTree[node]

def findMaxValue(segmentTree, node, left, right, start, end):
if left > end or right < start:
return -1
if start <= left and right <= end:
return segmentTree[node]

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

def initMinSegmentTree(arr, segmentTree, node, left, right):
if left == right:
segmentTree[node] = arr[left]
else:
mid = (left + right) // 2
segmentTree[node] = min(initMinSegmentTree(arr, segmentTree, node * 2, left, mid), initMinSegmentTree(arr, segmentTree, node * 2 + 1, mid + 1, right))
return segmentTree[node]

def findMinValue(segmentTree, node, left, right, start, end):
if left > end or right < start:
return 314159265359
if start <= left and right <= end:
return segmentTree[node]

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

def solution():
N, M = map(int, sys.stdin.readline().split())

arr = []
for _ in range(N):
arr.append(int(sys.stdin.readline()))

height = int(math.ceil(math.log2(N)))
treeSize = 1 << (height + 1)

segmentMinTree = [0] * treeSize
segmentMaxTree = [0] * treeSize

initMinSegmentTree(arr, segmentMinTree, 1, 0, N-1)
initMaxSegmentTree(arr, segmentMaxTree, 1, 0, N-1)

for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
print("{0} {1}".format(findMinValue(segmentMinTree, 1, 0, N-1, a-1, b-1), findMaxValue(segmentMaxTree, 1, 0, N-1, a-1, b-1)))

solution()
``````

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

Categories:

Updated: