[자료구조] 백준 14427번: 수열과 쿼리 15 (C++)

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

14427번: 수열과 쿼리 15

이번 문제는 두 개의 포인트가 있었다.

• 1~n까지 중 최솟값을 찾는 거라 따로 쿼리 함수가 필요 없다.
• 배열의 인덱스를 노드에 담아야 한다.

처음에는 배열의 인덱스를 어떻게 반환할까 생각하다가 그냥 함수 하나 만들었다.

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

a와 b 인덱스를 넣어서 배열 값들을 비교해준 뒤에 작은 값에 대한 인덱스를 반환해주었다.

 

[update: 실수]

문제가 풀리고 나서 보았을 때, 왜 이런 실수를 한 거지라는 생각을 했다.

arr[0] = INF;

ll update(ll start, ll end, ll node, ll index) {
	if (index < start || end < index) return 0;
	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));
}

구간을 벗어난 노드에 대해서 0을 리턴하는데 0에는 INF(1000000000 + 1)의 배열 값을 담아두었다.

저렇게 되면 업데이트되는 index가 무조건 제일 최솟값이 되는 값을 가지고 있다는 게 되는데

왜 이런 생각을 했는지 모르겠다.

범위를 벗어난 노드에 대해서는 그 구간에 해당하는 노드를 반환해주면 된다.

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));
}

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (100000 + 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 main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	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 {
			cout << sgTree[1] << '\n';
		}
	}
	return 0;
}