[백준/BOJ] 백준 2357번 : 최솟값과 최댓값

www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

최솟값 세그먼트 트리와 최댓값 세그먼트 트리를 만들어서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> maxsgmtt;
vector<int> minsgmtt;
vector<int> input_data;

int Make_minsgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return minsgmtt[here] = input_data[range_left];

	int mid = (range_left + range_right) / 2;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return minsgmtt[here] = min(Make_minsgmtt(left_child, range_left, mid), Make_minsgmtt(right_child, mid + 1, range_right));
}

int Query_minsgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 1000000001;

	if (find_left <= range_left && range_right <= find_right)
		return minsgmtt[here];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return min(Query_minsgmtt(left_child, range_left, mid, find_left, find_right), Query_minsgmtt(right_child, mid + 1, range_right, find_left, find_right));
}

int Make_maxsgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return maxsgmtt[here] = input_data[range_left];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return maxsgmtt[here] = max(Make_maxsgmtt(left_child, range_left, mid), Make_maxsgmtt(right_child, mid + 1, range_right));
}

int Query_maxsgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return -1;

	if (find_left <= range_left && range_right <= find_right)
		return maxsgmtt[here];

	int mid = (range_left + range_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return max(Query_maxsgmtt(left_child, range_left, mid, find_left, find_right), Query_maxsgmtt(right_child, mid + 1, range_right, find_left, find_right));
}

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

	cin >> n >> m;

	//세그먼트 트리의 크기를 넉넉하게 n*4로 하였다.
	maxsgmtt.resize(n * 4); 
	minsgmtt.resize(n * 4);

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		input_data.push_back(input);
	}

	//최솟값, 최댓값 세그먼트 트리 만들기
	Make_minsgmtt(0, 0, n - 1);
	Make_maxsgmtt(0, 0, n - 1);

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

		cout << Query_minsgmtt(0, 0, n - 1, a - 1, b - 1) << " " << Query_maxsgmtt(0, 0, n - 1, a - 1, b - 1) << "\n";
	}

	return 0;
}