[백준/BOJ] 백준 10868번 : 최솟값

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

10868번: 최솟값

세그먼트 트리를 이용해서 문제를 해결했다.

 

코드

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

int n, m;
vector<int> number;
vector<int> sgmtt;
vector<int> result;

int Make_sgmtt(int here, int index_left, int index_right)
{
	if (index_left == index_right)
		return sgmtt[here] = number[index_left];

	int index_mid = (index_left + index_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return sgmtt[here] = min(Make_sgmtt(left_child, index_left, index_mid), Make_sgmtt(right_child, index_mid + 1, index_right));
}

int Query_sgmtt(int here, int index_left, int index_right, int find_left, int find_right)
{
	if (find_right < index_left || index_right < find_left)
		return 1000000001;

	if (find_left <= index_left && index_right <= find_right)
		return sgmtt[here];

	int index_mid = (index_left + index_right) / 2;
	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;

	return min(Query_sgmtt(left_child, index_left, index_mid, find_left, find_right), Query_sgmtt(right_child, index_mid + 1, index_right, find_left, find_right));
}

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

	cin >> n >> m;

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

		number.push_back(input);
	}

	sgmtt.resize(n * 4); //세그먼트 트리의 크기는 넉넉하게 n * 4로 한다
	Make_sgmtt(0, 0, n - 1);

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

		int query_ret = Query_sgmtt(0, 0, n - 1, a - 1, b - 1);
		result.push_back(query_ret);
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << "\n";

	return 0;
}