백준 14428번 수열과 쿼리 16 C++ 세그먼트 트리

리뷰

세그먼트 트리를 통한 최소값을 찾고, 해당 값의 index를 찾는 문제

 

문제 풀이

1. n값을 입력받고 n개의 수를 1차 벡터에  입력 받는다, tree는 4 * n 사이즈로 초기화 해준 뒤 build를 진행한다.
2. 이때 tree는 vector<pair<int, int>> 타입으로 최솟값과 해당 index를 모두 저장할 수 있게 해준다.
3. m개의 줄에 걸쳐 쿼리를 받아주고 각 첫번째 숫자에 따라 업데이트 및 출력을 해주면 된다.
4. 쿼리 함수를 실행할때도 리턴 형식을 pair<int, int>로 해주고 출력 시엔 second + 1을 해주면 된다.

 

참고 사항

	ios::sync_with_stdio(false);
	cin.tie(NULL);

 

이건 꼭 해주기

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<pair<int, int>> tree;

void build(vector<int>& lst, int node, int start, int end) {
	if (start == end) {
		tree[node] = { lst[start], start };
	}
	else {
		int mid = (start + end) / 2;
		build(lst, node * 2, start, mid);
		build(lst, node * 2 + 1, mid + 1, end);
		tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

void update(int node, int start, int end, int idx, int val) {
	if (start == end) {
		tree[node] = { val, idx };
	}
	else {
		int mid = (start + end) / 2;
		if (start <= idx && idx <= mid) {
			update(node * 2, start, mid, idx, val);
		}
		else {
			update(node * 2 + 1, mid + 1, end, idx, val);
		}
		tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
	}
}

pair<int, int> query(int node, int start, int end, int L, int R) {
	if (R < start || end < L) {
		return { 1000000001, 100001 };
	}
	if (L <= start && end <= R) {
		return tree[node];
	}
	int mid = (start + end) / 2;
	pair<int, int> left = query(node * 2, start, mid, L, R);
	pair<int, int> right = query(node * 2 + 1, mid + 1, end, L, R);
	return min(left, right);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	vector<int> lst(n);
	tree.resize(4 * n);
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
	}
	build(lst, 1, 0, n - 1);
	cin >> m;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(1, 0, n - 1, b - 1, c);
		}
		else {
			cout << query(1, 0, n - 1, b - 1, c - 1).second + 1 << "\n";
		}
	}
}