[P4] 백준 5817번 고통받는 난쟁이들 C++ 세그먼트 트리

리뷰

 

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

각 난쟁이의 키와 인덱스를 별도로 저장하고, max, min값의 세그먼트 트리를 통해 연속 여부를 체크하는 문제

 

 

전역 변수

• n : 난쟁이의 인원 수를 저장할 변수
• m : 쿼리의 개수를 저장할 변수
• N : 배열 및 트리의 최대 크기를 저장할 변수
• lst : 인덱스를 난쟁이의 키로, 값을 난쟁이의 위치로 저장할 정수형 배열
• idx : 인덱스를 난쟁이의 위치로, 값을 난쟁이의 키로 저장할 정수형 배열
• tree : 세그먼트 트리의 최대, 최소값 정보를 저장하기 위한 pair<int, int>타입의 배열

 

함수

1. build

void build(int node, int s, int e)

 

세그먼트 트리를 초기화 하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e를 전달받는다.
2. 기저 조건으로 리프 노드에 도달했을 경우 현재 노드의 최대값과 최소값을 lst의 s값으로 저장한다.
3. 기저 조건이 아니라면 좌, 우 자식 노드로 재귀를 진행해 준다.
4. 재귀를 빠져나오며 현재 노드를 자식 노드의 최대값과 최소값으로 저장해 준다.

 

2. update

void update(int node, int s, int e, int idx, int val)

 

세그먼트 트리 정보를 변경하고 최신화를 진행하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 변경할 난쟁이 키 idx, 변경할 난쟁이 위치 val을 전달받는다.
2. 기저 조건으로 리프 노드에 도달했을 경우 현재 노드의 최대값과 최소값을 모두 val로 변경해 준다.
3. 기저 조건이 아니라면 현재 탐색 범위의 절반을 변수 mid에 저장해 준다.
4. idx가 mid보다 작거나 같다면 왼쪽으로, 크다면 오른쪽으로 재귀를 진행해 준다.
5. 재귀를 빠져나오며 현재 노드를 자식 노드의 최대값과 최소값으로 저장해 준다.

 

3. query

pair<int, int> query(int node, int s, int e, int L, int R)

 

세그먼트 트리의 구간을 탐색하며 난쟁이 위치의 최소값과 최대값을 탐색하는 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 난쟁이 키의 구간 L, R을 전달받는다.
2. 첫 번째 기저 조건으로 범위를 벗어난 경우 최대값은 1 미만, 최소값은 20만 초과 값을 리턴한다.
3. 두 번째 기저 조건으로 탐색 범위가 난쟁이 키의 구간에 포함된다면 현재 노드를 리턴한다.
4. 기저 조건에 만족하지 않는 경우 좌, 우 자식 노드로 재귀를 진행하고 각각의 결과를 left, right에 저장한다.
5. 두 자식 노드의 최대값과 최소값을 찾아 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n개의 요소를 idx배열에 입력 받는다, lst의 idx인덱스의 값은 i로 저장해 준다.
2. build 함수를 통해 세그먼트 트리 정보를 초기화 해준다.
3. m번의 while루프를 수행하고 각 쿼리 정보를 변수 op, x, y에 입력 받아준다.
4. op가 1일 경우 update함수를 통해 세그먼트 트리의 난쟁이 키가 idx[x], idx[y]인 난쟁이의 위치를 y, x로 변경해 준다.
5. swap메서드를 통해 lst의 idx[x], idx[y]값을 서로 변경해 준다, 이후 idx[x], idx[y]값도 서로 변경해 준다.
6. op가 2일 경우 query함수를 통해 난쟁이의 키가 x, y 사이인 난쟁이의 위치의 최대, 최소값을 변수 result에 저장해 준다.
7. 만약 result 최대값과 최소값의 차가 y - x와 동일하다면 YES를, 아니라면 NO를 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 키와 위치를 모두 알아야 하기 때문에 두 개의 배열 혹은 벡터를 활용해 주어야 한다.
• 세그먼트 트리는 난쟁이의 키를 기준으로 인덱싱을 하고, 값은 난쟁이의 위치를 기록하고 있어야 한다.
• 결국 키가 A ~ B인 난쟁이가 서로 이웃해 있으려면 해당 난쟁이들의 위치의 최소, 최대값의 차가 B - A와 동일해야 한다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, m;
const int N = 200001;
int lst[N];
int idx[N];
pair<int, int> tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = { lst[s], lst[s] };
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = { max(tree[node * 2].first, tree[node * 2 + 1].first), min(tree[node * 2].second, tree[node * 2 + 1].second) };
	}
}

void update(int node, int s, int e, int idx, int val) {
	if (s == e) tree[node] = { val, val };
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx, val);
		else update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = { max(tree[node * 2].first, tree[node * 2 + 1].first), min(tree[node * 2].second, tree[node * 2 + 1].second) };
	}
}

pair<int, int> query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return { -1, 200001 };
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	pair<int, int> left = query(node * 2, s, mid, L, R);
	pair<int, int> right = query(node * 2 + 1, mid + 1, e, L, R);
	return { max(left.first, right.first), min(left.second, right.second) };
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> idx[i];
		lst[idx[i]] = i;
	}
	build(1, 1, n);
	while (m--) {
		int op, x, y; cin >> op >> x >> y;
		if (op == 1) {
			update(1, 1, n, idx[x], y);
			update(1, 1, n, idx[y], x);
			swap(lst[idx[x]], lst[idx[y]]);
			swap(idx[x], idx[y]);
		}
		else {
			pair<int, int> result = query(1, 1, n, x, y);
			if (result.first - result.second == y - x) cout << "YES\n";
			else cout << "NO\n";
		}
	}
}