백준 No.14427 [수열과 쿼리 15]

Baekjoon Online Judge No.14427 [수열과 쿼리 15]

---

  문제 

14427번: 수열과 쿼리 15 (acmicpc.net)

14427번: 수열과 쿼리 15

---

  설명 

<알고리즘 분류>

* 세그먼트 트리 (Segment tree)

  기본적인 세그먼트 트리 자료구조를 통해 풀 수 있는 문제이다.

 

1. 트리의 노드들에 그 노드에 해당하는 수열의 영역 내에서 최소값을 가지는 원소의 {값, 인덱스} 를 저장한다. 최소값을 저장하는 조건은 문제의 요구대로 아래 좌측, 우측 좌식 노드 중 더 작은 값을 가지는 노드를 선택하고 두 노드 모두 같은 값을 가지고 있다면, 더 작은 인덱스를 가지고 있는 노드를 선택한다.

 

2. 이러한 규칙으로 리프노드가 아닌 내부 임의의 노드가 두 자식노드의 값을 가진다면 최종적으로 루트노드는 입력되는 수열에서 가장 최소값에 해당되는 {값, 인덱스} 를 가질 것 이다.

 

3. 수열에서 원하는 인덱스의 원소에 해당하는 값을 변경할 때에는 리프노드에서 해당되는 노드부터 시작해서 루트노드까지 트리의 노드들을 업데이트 해 주면 된다. 변경하고자 하는 인덱스에 해당되는 리프노드는 바뀌는 값으로 변경만 하면 되고, 이 리프노드의 조상 노드들은 처음에 트리 노드를 초기화 하는 조건으로 루트노드까지 초기화를 다시 해 나가면 된다.

 

<Example>

  위 수열에 대한 세그먼트 트리를 예시로 구현 해 보았다.

---

  Code 

#include <iostream>
#include <vector>
#include <cmath>
#define val first
#define idx second

using namespace std;
typedef pair<int, int> pii;

vector<pii> tree;
vector<int> List;
const int inf = 1000000001;
int n, m, s;

void update(int tarIdx, int tarVal) {
	int curIdx = ::s + tarIdx - 1;
	tree[curIdx].val = tarVal;
	curIdx >>= 1;

	pii left, right;

	while (curIdx) {
		left = tree[curIdx << 1];
		right = tree[(curIdx << 1) + 1];

		if (left.val < right.val) tree[curIdx] = left;
		else if (right.val < left.val) tree[curIdx] = right;
		else {
			if (left.idx < right.idx) tree[curIdx] = left;
			else tree[curIdx] = right;
		}

		curIdx >>= 1;
	}
}

void init() {
	int cur = s - 1;
	pii left, right;
	while (cur--) {
		left = tree[cur << 1];
		right = tree[(cur << 1) + 1];

		if (left.val < right.val) tree[cur] = left;
		else if (right.val < left.val) tree[cur] = right;
		else {
			if (left.idx < right.idx) tree[cur] = left;
			else tree[cur] = right;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;

	::s = pow(2, ceil(log2(n)));

	tree.assign(s << 1, pii{inf, 0});
	List.assign(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		cin >> List[i];
		tree[s + i - 1] = { List[i], i };
	}

	init();

	cin >> m;

	int select, i, k;
	while (m--) {
		cin >> select;

		if (select & 1) {
			cin >> i >> k;
			update(i, k);
		}
		else {
			cout << tree[1].idx << '\n';
		}
	}
}