[백준] [C++] 2357번 최솟값과 최댓값 (segment tree)
2021. 7. 10. 20:21ㆍ카테고리 없음
1. 문제
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
2. 구간트리 구성
이 문제는 구간에서의 최솟값과 최댓값을 구하는 문제이다
각 구간을 이진 트리로 구성하여
재귀함수를 통해 밑바닥에서부터 차근차근 최솟값과 최댓값을 pair에 담아 저장하여
문제를 해결 할 수 있다.
3. 구간의 최솟값과 최댓값 찾기
루트인 전체 구간에서부터 시작하여 문제를 해결해나간다.
구간이 주어지면 다음과 같은 부분문제들이 생긴다
1) 왼쪽에 있을 경우
2) 중간에 있을 경우
3) 오른쪽에 있을 경우
여기서 중요한것은 중간에 걸쳐 있는 부분문제이다.
이 부분에서는 mid를 중심으로 두 개의 pair값이 나오는데,
이 둘 값중 최소 최대인것을 다시 찾으면 문제를 해결할 수 있다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
vector<int> number;
vector<pair<int, int> > segTree;
pair<int, int> init(int lo, int hi, int idx){
if(lo + 1 == hi) {
return segTree[idx] = {number[lo], number[lo]};
}
int mid = (lo + hi) / 2;
pair<int, int> left = init(lo, mid, idx * 2);
pair<int, int> right = init(mid, hi, idx * 2 + 1);
int minimum = min(left.first, right.first);
int maximum = max(left.second, right.second);
segTree[idx] = {minimum, maximum};
return segTree[idx];
}
pair<int, int> query(int lo, int hi, int idx, int start, int end) {
if(lo >= start && end >= hi) {
return segTree[idx];
}
int mid = (lo + hi) / 2;
if(end <= mid) {
return query(lo, mid, idx*2, start, end);
}
else if(mid <= start) {
return query(mid, hi, idx*2 + 1, start, end);
}
else {
pair<int, int> left = query(lo, mid, idx * 2, start, mid);
pair<int, int> right = query(mid, hi, idx * 2 + 1, mid, end);
int minimum = min(left.first, right.first);
int maximum = max(left.second, right.second);
return {minimum, maximum};
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin>>N>>M;
number = vector<int>(N);
segTree = vector<pair<int, int> >(N*4);
for(int i = 0; i < N; i++) {
cin>>number[i];
}
init(0, N, 1);
for(int i = 0; i < M; i++) {
int a, b;
cin>>a>>b;
if(a > b) {
swap(a, b);
}
pair<int, int> answer = query(0, N, 1, a - 1, b);
cout<<answer.first<<" "<<answer.second<<"\n";
}
}
|
cs |