[백준/BOJ] 백준 20933번 : 마스크펑크 2077

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

20933번: 마스크펑크 2077

 

구간의 범위에 대해 마스크 생산 비용의 최솟값 세그먼트 트리와, 이동시간의 합 세그먼트 트리를 만들었다. 그리고 난 뒤, 주어진 시간 내에 이동할 수 있는 범위를 이분 탐색을 통해 구하고 구한 범위의 최소 마스크 가격을 세그먼트 트리의 쿼리를 통해 찾아서 문제를 해결했다.

 

코드

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

int n;
vector<int> c;
vector<int> t;
vector<int> c_min_sgmtt(400000);
vector<int> t_sum_sgmtt(400000);
int q;
vector<int> result;

int MakeCMinSgmtt(int here, int range_left, int range_right) {

	if (range_left == range_right) {
		return c_min_sgmtt[here] = c[range_left];
	}

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

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

int QueryCMinSgmtt(int here, int range_left, int range_right, int find_left, int find_right) {

	if (find_right < range_left || range_right < find_left) {
		return numeric_limits<int>::max();
	}

	if (find_left <= range_left && range_right <= find_right) {
		return c_min_sgmtt[here];
	}

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

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

int MakeTSumSgmtt(int here, int range_left, int range_right) {

	if (range_left == range_right) {
		return t_sum_sgmtt[here] = t[range_left];
	}

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

	return t_sum_sgmtt[here] = (MakeTSumSgmtt(left_child, range_left, mid) + MakeTSumSgmtt(right_child, mid + 1, range_right));
}

int UpdataTSumSgmtt(int here, int range_left, int range_right, int find_index, int value) {

	if (range_left == range_right && range_right == find_index) {
		return t_sum_sgmtt[here] = value;
	}

	if (find_index < range_left || range_right < find_index) {
		return t_sum_sgmtt[here];
	}

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

	return t_sum_sgmtt[here] = (UpdataTSumSgmtt(left_child, range_left, mid, find_index, value) + UpdataTSumSgmtt(right_child, mid + 1, range_right, find_index, value));
}

int QueryTSumSgmtt(int here, int range_left, int range_right, int find_left, int find_right) {

	if (find_right < range_left || range_right < find_left) {
		return 0;
	}

	if (find_left <= range_left && range_right <= find_right) {
		return t_sum_sgmtt[here];
	}

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

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

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

	cin >> n;

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

		c.push_back(input);
	}

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

		t.push_back(input);
	}

	MakeCMinSgmtt(0, 0, n - 1); //마스크 생산 비용의 최소값 세그먼트 트리 만들기
	MakeTSumSgmtt(0, 0, n - 2); //이동시간의 합 세그먼트 트리 만들기

	cin >> q;

	for (int i = 0; i < q; i++) {
		string order;
		int x, input;

		cin >> order >> x >> input;
		x--; //첫번째 집을 0번으로 했기 때문에 -1 처리

		if (order == "UPDATE") { 
			UpdataTSumSgmtt(0, 0, n - 2, x, input); //이동시간 합 세그먼트 트리 업데이트
		}

		else {
			int left;
			int right;
			int mid;
			int check_left;
			int check_right;

			//x지점을 기준으로 왼쪽으로 input분 이내 이동할 수 있는 가장 왼쪽을 찾는다
			left = 0;
			right = x - 1;
			check_left = x;
			while (left <= right) {
				mid = (left + right) / 2;

				//mid ~ x 사이의 이동 시간의 합이 input분 이내인지 확인한다

				//input분 이내로 가능할때
				if (QueryTSumSgmtt(0, 0, n - 2, mid, x - 1) <= input) {
					check_left = mid;
					right = mid - 1;
				}

				else {
					left = mid + 1;
				}
			}

			//x지점을 기준으로 오른쪽으로 input분 이내 이동할 수 있는 가장 오른쪽을 찾는다
			left = x;
			right = n - 2;
			check_right = x;
			while (left <= right) {
				mid = (left + right) / 2;

				//x ~ mid+1 사이의 이동 시간의 합이 input분 이내인지 확인한다

				//input분 이내로 가능할때
				if (QueryTSumSgmtt(0, 0, n - 2, x, mid) <= input) {
					check_right = mid + 1;
					left = mid + 1;
				}

				else {
					right = mid - 1;
				}
			}

			//input이내의 시간에 이동할 수 있는 범위에서 최소 마스크 가격을 찾는다
			int this_result = QueryCMinSgmtt(0, 0, n - 1, check_left, check_right);
			result.push_back(this_result);
		}
	}

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

	return 0;
}