[PS] 백준 2357 - 최댓값과 최솟값

📌 알고리즘 분류

해당 문제는 세그먼트 트리에 대한 이해가 필요한 문제입니다.
세그먼트 트리

📖 문제

백준 2357번

N개의 데이터에서 a번째 부터 b번째 까지의 최솟값과 최댓값을 M개 출력하는 문제입니다. 시간제한이 있는 문제이기 때문에 O(N)의 시간 복잡도를 가지는 선형구조로는 해당 문제를 푸는 게 불가능합니다. 따라서 데이터를 바탕으로 세그먼트 트리를 생성한 이후에 접근해야 합니다.

💻 코드

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int v[100001];
int mintree[400010];
int maxtree[400010];

int min_segment_tree(int start, int end, int node)
{
	if (start == end)
		return mintree[node] = v[start];

	int mid = (start + end) / 2;

	return mintree[node] = min(min_segment_tree(start, mid, node * 2), min_segment_tree(mid + 1, end, node * 2 + 1));
}

int max_segment_tree(int start, int end, int node)
{
	if (start == end)
		return maxtree[node] = v[start];

	int mid = (start + end) / 2;

	return maxtree[node] = max(max_segment_tree(start, mid, node * 2), max_segment_tree(mid + 1, end, node * 2 + 1));
}

int find_min(int start, int end, int node, int left, int right)
{
	if (left > end || right < start)
		return INT_MAX;

	if (left <= start && end <= right)
		return mintree[node];

	int mid = (start + end) / 2;

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

int find_max(int start, int end, int node, int left, int right)
{
	if (left > end || right < start)
		return 0;

	if (left <= start && end <= right)
		return maxtree[node];

	int mid = (start + end) / 2;

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

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

	for (int i = 0; i < 500000; i++)
	{
		mintree[i] = INT_MAX;
		maxtree[i] = 0;
	}

	cin >> n >> m;

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

	min_segment_tree(1, n, 1);
	max_segment_tree(1, n, 1);

	int a, b;

	for(int i =0;i<m;i++)
	{
		cin >> a >> b;
		cout << find_min(1, n, 1, a, b) << " " << find_max(1,n,1,a,b);
		cout << "\n";
	}
}