백준 2357번 - 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

 

풀이

Min, Max Segment Tree를 사용한 문제이다.

 

Min, Max Segment Tree란 각 범위의 최소값과 최대값을 가지고 있는 세그먼트 트리를 말한다.

 

두 개의 세그먼트 트리를 만들 수도 있지만 코드가 길어질 것 같아서 pair를 사용해 하나의 트리로 만들었다.

 

구현은 일반적인 세그트리와 비슷하다.

 

세그트리 자체를 이해했다면 이 코드 역시 이해하기 어렵지 않을 것이다.

 

참고로 비슷하게 짰는데 시간초과가 난다면 아래의 코드를 붙여서 돌려보면 통과할 수도 있다!

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int INF = INT_MAX;

vector<ll>arr(100007);
vector<pll>MinMaxTree(300007); // min = first, max = second

pll init(int node, int start, int end) {
	if (start == end) { // 리프 노드
		return MinMaxTree[node] = pll(arr[start], arr[start]);
	}
	else {
		pll left = init(node * 2, start, (start + end) / 2), right = init(node * 2 + 1, (start + end) / 2 + 1, end);
		return MinMaxTree[node] = pll(min(left.first, right.first), max(left.second, right.second));
	}
}

pll query(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return pll(INF, 0);
	if (left <= start && end <= right) return MinMaxTree[node];
	pll l = query(node * 2, start, (start + end) / 2, left, right), r = query(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
	return pll(min(l.first, r.first), max(l.second, r.second));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	init(1, 0, n - 1);
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		pll ans = query(1, 0, n - 1, a - 1, b - 1);
		cout << ans.first << " " << ans.second << "\n";
	}
}

 

update는 이 문제에서 나오지 않았지만 다른 난이도 있는 문제를 풀 때에는 update 함수가 꼭 필요할 것이다.

아래는 index번째 수를 num으로 교체하기 위해 사용할 수 있는 update에 대해 구현한 것이다.

pll update(int node, int start, int end, int index, ll num) {
	if (index < start || end < index) return MinMaxTree[node];
	if (start == end) MinMaxTree[node] = pll(num, num);
	else {
		pll left = update(node * 2, start, (start + end) / 2, index, num);
		pll right = update(node * 2 + 1, (start + end) / 2 + 1, end, index, num);
		MinMaxTree[node].first = min(left.first, right.first);
		MinMaxTree[node].second = max(left.second, right.second);
	}
	return MinMaxTree[node];
}

만약 update 해야 하는 범위에 속하지 않는다면 건너뛰고

포함된다면 리프 노드인지 아닌지에 따라 update하면 된다.

 

그림을 그려보면서 이해하는걸 추천한다.