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

2357번: 최솟값과 최댓값

세그먼트 트리를 이용한 문제이다. 해당 구간의 최댓값과 최솟값을 구해 세그먼트 트리를 만들어주고 입력받은 a, b에 해당하는 결과를 찾아 출력해주었다.
생각보다 어려웠던 문제였다. 세그먼트 트리를 이용하는 것까지는 생각을 해냈었는데 결과를 찾는 과정에서 좀 해맸었다. 세그먼트 트리에 대해 잘 알아두어야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> n;
vector<pair<int, int>> m;
vector<pair<int, int>> tree;

pair<int, int> createTree(int start, int end, int idx) {
	if (start == end) return tree[idx] = { n[start], n[start] };

	int mid = (start + end) / 2;

	pair<int, int> a = createTree(start, mid, idx * 2);
	pair<int, int> b = createTree(mid + 1, end, idx * 2 + 1);

	int min_value = a.first < b.first ? a.first : b.first;
	int max_value = a.second > b.second ? a.second : b.second;

	return tree[idx] = { min_value, max_value };
}

pair<int, int> findTree(int start, int end, int a, int b, int idx) {
	if (start > b || end < a) return { 1e9, 0 };
	if (a <= start && end <= b) return tree[idx];

	int mid = (start + end) / 2;

	pair<int, int> node1 = findTree(start, mid, a, b, idx * 2);
	pair<int, int> node2 = findTree(mid + 1, end, a, b, idx * 2 + 1);

	int min_value = node1.first < node2.first ? node1.first : node2.first;
	int max_value = node1.second > node2.second ? node1.second : node2.second;

	return { min_value, max_value };
}

void solution() {
	tree.resize(N * 4);
	createTree(1, N, 1);

	for (int i = 0; i < M; i++) {
		int a = m[i].first;
		int b = m[i].second;

		pair<int, int> result = findTree(1, N, a, b, 1);
		cout << result.first << " " << result.second << "\n";
	}
}

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

	cin >> N >> M;

	n.push_back(-1);
	int c;
	for (int i = 0; i < N; i++) {
		cin >> c;
		n.push_back(c);
	}

	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		m.push_back({ a, b });
	}

	solution();
	
	return 0;
}