2357번: 최솟값과 최댓값
접근 방법
구간합 세그먼트 트리를 약간 바꾸어 생각해서, 부모는 자식의 합을 저장하는 것이 아닌 최댓값과 최솟값을 저장하도록 구현하여 해결할 수 있습니다.
코드
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
#define endl '\\n'
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
/* - GLOBAL VARIABLES ---------------------------- */
int x;
vector<int> max_seg, min_seg;
/* ----------------------------------------------- */
/* - FUNCTIONS ----------------------------------- */
int query_max(int l, int r) {
l+=x-1;
r+=x-1;
int value = 0;
while(l <= r) {
if(l%2 == 1) {
value = max(max_seg[l], value);
}
if(r%2 == 0) {
value = max(max_seg[r], value);
}
l = (l+1)/2;
r = (r-1)/2;
}
return value;
}
int query_min(int l, int r) {
l+=x-1;
r+=x-1;
int value = INT_MAX;
while(l <= r) {
if(l%2 == 1) {
value = min(min_seg[l], value);
}
if(r%2 == 0) {
value = min(min_seg[r], value);
}
l = (l+1)/2;
r = (r-1)/2;
}
return value;
}
/* ----------------------------------------------- */
#define SUBMIT
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#ifndef SUBMIT
(void)!freopen("input.txt", "r", stdin);
cout << "# From the test case" << endl;
#endif
int N, M; cin >> N >> M;
max_seg = vector<int>(4 * N, 0);
min_seg = vector<int>(4 * N, INT_MAX);
for(x = 1; x <= N; x*=2);
int temp;
for(int i = x; i < x + N; ++i) {
cin >> temp;
max_seg[i] = temp;
min_seg[i] = temp;
}
for(int i = x-1; i > 0; --i) {
max_seg[i] = max(max_seg[i*2], max_seg[i*2 + 1]);
min_seg[i] = min(min_seg[i*2], min_seg[i*2 + 1]);
}
int a, b;
for(int i = 0; i < M; ++i) {
cin >> a >> b;
cout << query_min(a, b) << ' ' << query_max(a, b) << endl;
}
return 0;
}
|