[자료구조] 백준 2357번: 최솟값과 최댓값 (C++)

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

2357번: 최솟값과 최댓값

최솟값은 전 포스팅과 똑같은 문제이고, 최댓값은 세그먼트 트리를 구한 후, 값을 찾는 함수에서

영역을 벗어난 경우 0을 리턴해주는 게 최솟값과 다른 점이다.

#include <iostream>
#define MAX 100000 + 1
#define INF 1000000000 + 1
using namespace std;

long long minTree[4 * MAX];
long long maxTree[4 * MAX];
long long arr[MAX];

int n, m;

//== Segment Tree INIT == (각 노드에 구간 최솟값)
long long minInit(int start, int end, int node) {
	if (start == end) {
		return minTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

long long maxInit(int start, int end, int node) {
	if (start == end) {
		return maxTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

long long findMinValue(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INF;
	if (left <= start && right >= end) return minTree[node];
	int mid = (start + end) / 2;
	return min(findMinValue(start, mid, node * 2, left, right),
		findMinValue(mid + 1, end, node * 2 + 1, left, right));
}

long long findMaxValue(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;
	if (left <= start && right >= end) return maxTree[node];
	int mid = (start + end) / 2;
	return max(findMaxValue(start, mid, node * 2, left, right),
		findMaxValue(mid + 1, end, node * 2 + 1, left, right));
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	minInit(1, n, 1);
	maxInit(1, n, 1);

	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		cout << findMinValue(1, n, 1, a, b) << ' ';
		cout << findMaxValue(1, n, 1, a, b) << '\n';
	}
}