[백준][C++] 14438: 수열과 쿼리 17

문제 링크: https://www.acmicpc.net/problem/14438

 

세그먼트 트리 문제입니다. 최솟값 구하는 세그먼트 트리 만들면 됩니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;




// minimum
vector<int> tree;

// node -> 1
// [node_l, node_r] -> [0, n-1]
int init(vector<int>& arr, int node_l, int node_r, int node) {
	if (node_l == node_r) return tree[node] = arr[node_l];

	int mid = (node_l + node_r) / 2;
	return tree[node] = min(init(arr, node_l, mid, node * 2), init(arr, mid + 1, node_r, node * 2 + 1));
}

int query(const int& l, const int& r, int node_l, int node_r, int node) {
	if (r < node_l || node_r < l) return INT_MAX;	// 구간과 겹치지 않는 경우
	if (l <= node_l && node_r <= r) return tree[node];	// node 표현범위가 arr[l, r]에 포함되는 경우

	int mid = (node_l + node_r) / 2;
	return min(query(l, r, node_l, mid, node * 2), query(l, r, mid + 1, node_r, node * 2 + 1));
}

int update(const int& idx, const int& newValue, int node_l, int node_r, int node) {
	if (idx < node_l || node_r < idx) return tree[node];	// 구간과 겹치지 않는 경우
	if (node_l == node_r) return tree[node] = newValue;		// leaf

	int mid = (node_l + node_r) / 2;
	return tree[node] = min(update(idx, newValue, node_l, mid, node * 2), update(idx, newValue, mid + 1, node_r, node * 2 + 1));
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<int> arr(n);
	for (auto& c : arr)
		cin >> c;

	tree.resize(4 * n);
	init(arr, 0, n - 1, 1);

	int m;
	cin >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(b-1, c, 0, n-1, 1);
		}
		else {
			cout << query(b-1, c-1, 0, n-1, 1) << '\n';
		}
	}

	return 0;
}