문제
풀이
세그먼트 트리를 이용한 최솟값, 최댓값 구하기 문제이다. 파이썬 언어를 이용하였다. 기존 세그먼트 트리에서 구간에 대한 최솟값, 최댓값들을 저장해놓는다.
그 이후 왼쪽과 오른쪽을 비교하면서 최솟값, 최댓값을 구하면 되는 문제이다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import sys
from math import * #math 모듈에서 모든 함수를 가져온다.
def make_segment(node, start, end, T):
if(start == end):
if(T == False):
max_tree[node] = testcase[start]
return max_tree[node]
else:
min_tree[node] = testcase[start]
return min_tree[node]
mid = (start+end)//2
left_result = make_segment(2*node, start, mid, T)
right_result = make_segment(2*node+1, mid+1, end, T)
if(T == False):
max_tree[node] = max(left_result, right_result)
return max_tree[node]
else:
min_tree[node] = min(left_result, right_result)
return min_tree[node]
def query(node, start, end, left, right, T):
if(end < left or start > right):
if(T == False):
return -2e9
else:
return 2e9
if(left>=start and right<=end):
if(T == False):
return max_tree[node]
else:
return min_tree[node]
mid = (left + right) // 2
left_result = query(2*node, start, end, left, mid, T)
right_result = query(2*node+1, start, end, mid+1, right, T)
if(T == False):
return max(left_result, right_result)
else:
return min(left_result, right_result)
#n, m input
n, m = [int(x) for x in sys.stdin.readline().split()]
#n에 담길 testcase 어레이 선언
testcase = [0] * (n+1)
# 트리 높이, 트리 사이즈 선언
tree_height = (ceil)(log2(n))
tree_size = (1<<(tree_height + 1))
#max_tree, min_tree resize
min_tree = [0] * (tree_size+1)
max_tree = [0] * (tree_size+1)
#testcase에 원소 넣기
for i in range(1, n+1):
testcase[i] = (int(sys.stdin.readline()))
# min_tree, max_tree 형성(False == max, True == min)
make_segment(1, 1, n, False)
make_segment(1, 1, n, True)
#a, b 입력 받아 min값 max값 출력하기
for _ in range(m):
a, b = [int(x) for x in sys.stdin.readline().split()]
print(query(1, a, b, 1, n, True), end = ' ') # 기본값 엔터가 아닌 end = ' ' : 공백으로 끝내기
print(query(1, a, b, 1, n, False))
