[백준] 2357번 : 최솟값과 최대값

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

2357번: 최솟값과 최댓값

---

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;

ll init_min(vl& arr, vl& tree, int node, int start, int end) //최솟값 관련 트리
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;
	return tree[node] = min(init_min(arr, tree, node * 2, start, mid),init_min(arr, tree, node * 2 + 1, mid + 1, end));
}

ll init_max(vl& arr, vl& tree, int node, int start, int end) //최대값 관련 트리
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;
	return tree[node] = max(init_max(arr, tree, node * 2, start, mid), init_max(arr, tree, node * 2 + 1, mid + 1, end));
}

ll getMin(vl& tree, int node, int start, int end, int left, int right) //min 구하기
{
	if ((right < start) || (end < left))
		return 1e18;
	if ((left <= start) && (end <= right))
		return tree[node];
	int mid = (start + end) / 2;
	
	return min(getMin(tree, node * 2, start, mid, left, right), getMin(tree, node * 2 + 1, mid + 1, end, left, right));
}

ll getMax(vl& tree, int node, int start, int end, int left, int right) //max 구하기
{
	if ((right < start) || (end < left))
		return -1;
	if ((left <= start) && (end <= right))
		return tree[node];
	int mid = (start + end) / 2;

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

int main()
{

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;

	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));

	vl arr(n);
	vl tree1(tree_size);
	vl tree2(tree_size);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	init_min(arr, tree1, 1, 0, n - 1); //트리(min) 만들기
	init_max(arr, tree2, 1, 0, n - 1); //트리(max) 만들기
	for (int i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;
		cout << getMin(tree1, 1, 0, n - 1, a - 1, b - 1) << ' ';
		cout << getMax(tree2, 1, 0, n - 1, a - 1, b - 1) << '\n';
	}
}

 

> 세그먼트 트리를 이용하여 구현했습니다.

최대값을 구할때, 최솟값을 구할 때 필요한 각각의 트리 (tree1,tree2) 를 구현했고,

 

min을 구현할땐 min관련 트리인 tree1을 이용했고,

max 를 구현할땐 max 관련 트리인 tree2를 이용했습니다.