[백준/BOJ] 백준 14428번 : 수열과 쿼리 16

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

14428번: 수열과 쿼리 16

세그먼트 트리를 이용해 문제를 해결했다. 주어진 구간 중 크기가 가장 작은 값의 인덱스를 구하는 방법은 구간의 작은 값을 구하는 Query_sgmtt를 통해 Query_sgmtt의 결과가 더 작은쪽을 확인하는 방법(같은 값이라면 앞쪽을 확인한다)으로 문제를 해결했다.

 

코드

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

int n, m;
vector<int> a;
vector<int> sgmtt;
vector<int> output;

int Make_sgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return sgmtt[here] = a[range_left];

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

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

int Update_sgmtt(int here, int range_left, int range_right, int update_index)
{
	if (range_left == range_right && range_right == update_index)
		return sgmtt[here] = a[update_index];

	if (update_index < range_left || range_right < update_index)
	{
		return sgmtt[here];
	}

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

	return sgmtt[here] = min(Update_sgmtt(left_child, range_left, mid, update_index), Update_sgmtt(right_child, mid + 1, range_right, update_index));
}

int Query_sgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	if (find_right < range_left || range_right < find_left)
		return 1000000001;

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

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

int Solve(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (range_left == range_right)
		return range_left;

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

	//쿼리 결과가 더 작은쪽을 확인한다(같은 값이라면 앞쪽을 확인한다)
	if (Query_sgmtt(left_child, range_left, mid, find_left, find_right) <= Query_sgmtt(right_child, mid + 1, range_right, find_left, find_right))
		ret = Solve(left_child, range_left, mid, find_left, find_right);

	else
		ret = Solve(right_child, mid + 1, range_right, find_left, find_right);

	return ret;
}

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

	cin >> n;
	sgmtt.resize(n * 4); //세그먼트 트리의 크기를 넉넉하게 n * 4로 한다

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

		a.push_back(input);
	}

	Make_sgmtt(0, 0, n - 1);

	cin >> m;

	//문제에서 인덱스가 1부터 시작하는것을 고려한다
	for (int i = 0; i < m; i++)
	{
		int order, command1, command2;

		cin >> order >> command1 >> command2;

		if (order == 1)
		{
			a[command1 - 1] = command2;

			Update_sgmtt(0, 0, n - 1, command1 - 1);
		}

		else
		{
			int ret = Solve(0, 0, n - 1, command1 - 1, command2 - 1);
			output.push_back(ret + 1);
		}
	}

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


	return 0;
}