[자료구조] 백준 14428번: 수열과 쿼리 16 (C++), 인덱스 세그 트리

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

14428번: 수열과 쿼리 16

이번 문제에서 저번 수열과 쿼리 15에서 실수했던 update arr[0] = INF;를 쿼리에서 사용하면 된다.

(수열과 쿼리 15 포스팅: https://draw-code-boy.tistory.com/176)

#define INF (1000000000 + 1)
arr[0] = INF;

int query(int start, int end, int node, int left, int right) {
	if (start > right || end < left) return 0;
	if (left <= start && end <= right) {
		return sgTree[node];
	}
	int mid = (start + end) / 2;
	return compareMIN(query(start, mid, node * 2, left, right),
		query(mid + 1, end, node * 2 + 1, left, right));
}

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (100000 + 1)
#define INF (1000000000 + 1)
#define ll long long
using namespace std;

ll arr[MAX];
ll sgTree[MAX * 4];
ll n, m;

ll compareMIN(ll a, ll b) {
	if (arr[a] == arr[b]) return min(a, b);
	return arr[a] < arr[b] ? a : b;
}

ll sgInit(ll start, ll end, ll node) {
	if (start == end) {
		return sgTree[node] = start;
	}
	ll mid = (start + end) / 2;
	return sgTree[node] = compareMIN(sgInit(start, mid, node * 2),
		sgInit(mid + 1, end, node * 2 + 1));
}

ll update(ll start, ll end, ll node, ll index) {
	if (index < start || end < index) return sgTree[node];
	if (start == end) {
		return sgTree[node] = compareMIN(sgTree[node], index);
	}
	ll mid = (start + end) / 2;
	return sgTree[node] = compareMIN(update(start, mid, node * 2, index),
		update(mid + 1, end, node * 2 + 1, index));
}

int query(int start, int end, int node, int left, int right) {
	if (start > right || end < left) return 0;
	if (left <= start && end <= right) {
		return sgTree[node];
	}
	int mid = (start + end) / 2;
	return compareMIN(query(start, mid, node * 2, left, right),
		query(mid + 1, end, node * 2 + 1, left, right));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	arr[0] = INF;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	cin >> m;
	sgInit(1, n, 1);
	
	for (int i = 0, a; i < m; i++) {
		cin >> a;
		if (a == 1) {
			int b;
			ll c;
			cin >> b >> c;
			arr[b] = c;
			update(1, n, 1, b);
		}
		else {
			int b, c;
			cin >> b >> c;
			cout << query(1, n, 1, b, c) << '\n';
		}
	}
	return 0;
}