[백준] 최솟값과 최댓값

세그먼트 트리 문제를 하나 더 풀어봤다
이번 문제는 이전 구간 합을 구하는 문제에서 발전해서 두가지 조건 값을 찾는 문제이다.
그렇기 때문에 세그먼트 트리를 초기화 해줄 때, 하나의 값이 아닌 두개의 값(최소,최대)을 구해서 저장해두어야 한다.
하지만 방식 자체는 구간 합 구하기 문제와 다르지 않고 업데이트되는 것이 없다는 점에서 오히려 더 쉬운 문제라고 할수 있다.
탐색시 두개의 값을 좀더 수월하게 관리 할 수 있도록 구조체를 선언 해서 해당 문제를 해결 했다.

#include <iostream>.

using namespace std;

int MAX = 1'000'000'000;

struct S {
	int min;
	int max;
};

int nums[100'001];
S seg_tree[1 << 18];

//세그먼트 트리 초기화
S init_tree(int left,int right,int depth) {
	if (left == right) return seg_tree[depth] = { nums[left],nums[right] };

	int mid = (left + right) / 2;
	S set1 = init_tree(left, mid, depth * 2);
	S set2 = init_tree(mid + 1, right, depth * 2 + 1);

	return seg_tree[depth] = { (set1.min < set2.min ? set1.min : set2.min),(set1.max > set2.max ? set1.max : set2.max) };
}

// 구간 탐색
S search(int left, int right,int start,int end, int depth) {
	if (left > end || right < start)return { MAX,0 };
	if (left >= start && right <= end) return seg_tree[depth];

	int mid = (left + right) / 2;

	S set1 = search(left, mid, start, end, depth * 2);
	S set2 = search(mid + 1, right, start, end, depth * 2 + 1);

	return  { (set1.min < set2.min ? set1.min : set2.min),(set1.max > set2.max ? set1.max : set2.max) };
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
	}
	init_tree(1, N, 1);
	int a, b;
	while (M--) {
		cin >> a >> b;

		S result = search(1, N, a, b, 1);
		cout << result.min << " " << result.max << "\n";
	}

}