백준 2357 최솟값과 최댓값 (c++)

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

2357번: 최솟값과 최댓값

 

세그먼트 트리는 원래 O(N)이상 걸리는 작업들을 log 시간으로 해결할 수 있는 자료구조이다. 코딩테스트에 출제된다면 아마 모르면 맞아야지 문제이기 때문에 정답률이 처참할 것으로 예상된다. 하지만 세그먼트 트리를 응용까지 해서 풀어야하는 테스트는 아마도 카카오 네이버를 제외하면 거의 없을 거라 생각한다.

 

세그먼트 트리는 

1. 세그먼트 트리 빌드

2. 업데이트

3. 쿼리 수행

 

으로 구성된다. 그리고 세그먼트 트리는 완전이진트리이기 때문에 2^N - 1 개의 노드가 필요한데, 보통은 그냥 4 * N개로 생성해버린다.

 

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> isValueVector;

void build_segment_tree(vector<pair<int, int>>& seg_Tree, int start, int end, int node) {
	if (start == end) {
		seg_Tree[node].first = isValueVector[start];
		seg_Tree[node].second = isValueVector[start];
		return;
	}
	int mid = (start + end) / 2;
	build_segment_tree(seg_Tree, start, mid, node * 2);
	build_segment_tree(seg_Tree, mid + 1, end, node * 2 + 1);
	seg_Tree[node].first = max(seg_Tree[node * 2].first, seg_Tree[node * 2 + 1].first);
	seg_Tree[node].second = min(seg_Tree[node * 2].second, seg_Tree[node * 2 + 1].second);
}

void update(vector<pair<int, int>>& seg_Tree, int start, int end, int node, int index, int value) {
	int mid = (start + end) / 2;

	if (index < start || index > end) return;
	else if (start == end) {
		seg_Tree[node].first = value;
		seg_Tree[node].second = value;
	}
	else {
		update(seg_Tree, start, mid, node * 2, index, value);
		update(seg_Tree, mid + 1, end, node * 2 + 1 , index, value);
		seg_Tree[node].first = max(seg_Tree[node * 2].first, seg_Tree[node * 2 + 1].first);
		seg_Tree[node].second = min(seg_Tree[node * 2].second, seg_Tree[node * 2 + 1].second);
	}
}

int find_max_query(vector<pair<int, int>>& seg_Tree, int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;
	if (left <= start && end <= right) return seg_Tree[node].first;
	
	int mid = (start + end) / 2;

	return max(find_max_query(seg_Tree, start, mid, node * 2, left, right), find_max_query(seg_Tree, mid + 1, end, node * 2 + 1, left, right));
}

int find_min_query(vector<pair<int, int>>& seg_Tree, int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 1000000001;
	if (left <= start && end <= right) return seg_Tree[node].second;

	int mid = (start + end) / 2;

	return min(find_min_query(seg_Tree, start, mid, node * 2, left, right), find_min_query(seg_Tree, mid + 1, end, node * 2 + 1, left, right));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	/*int T; cin >> T;
	for (int t = 1; t <= T; t++) {	
		int n, m, tmp;
		cin >> n >> m;
		vector<pair<int, int>> seg_tree(n * 4);

		for (int i = 0; i < n; i++) {
			cin >> tmp;
			isValueVector.push_back(tmp);
		}

		build_segment_tree(seg_tree, 0, n - 1, 1);

		vector<int> answer;
		for (int i = 0; i < m; i++) {
			int order, x, y;
			cin >> order >> x >> y;
			if (order == 1) { // 쿼리
				answer.push_back(find_max_query(seg_tree, 0, n - 1, 1, x - 1, y - 1) - find_min_query(seg_tree, 0, n - 1, 1, x - 1, y - 1));
			}
			else {
				update(seg_tree, 0, n - 1, 1, x - 1, y);
				//for (auto a : seg_tree) cout << a.first << " " << a.second << " " << endl;
			}
		}

		cout << '#' << t << ' ';
		for (int ans : answer) cout << ans << ' ';
		cout << '\n';
	}*/

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;

		isValueVector.push_back(tmp);
	}

	vector<pair<int, int>> seg_tree(N * 4);

	build_segment_tree(seg_tree, 0, N - 1, 1);

	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;

		cout << find_min_query(seg_tree, 0, N - 1, 1, s - 1, e - 1) << ' ' << find_max_query(seg_tree, 0, N - 1, 1, s - 1, e - 1) << '\n';
	}
}