[백준 9345] 디지털 비디오 디스크(DVDs)

1. 문제 

 

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

9345번: 디지털 비디오 디스크(DVDs)

---

2. 풀이

 

세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자!

인덱스 트리 : https://kinngife.tistory.com/32

인덱스 트리 (Binary Indexed Tree)

 

0번부터 N-1번까지 총 N개의 DVD가 존재하고, 입력에 따라 2가지 행동이 존재한다. 

- 0 A B : A번 선반의 DVD와 B번 선반의 DVD를 바꾼다. 

- 1 A B : A번 선반부터 B번 선반까지 순서에 상관없이 A번 DVD부터 B번 DVD까지 모두 존재하면 YES, 존재하지 않으면 NO를 출력한다. 

 

대여점에서 일어나는 사건의 수 즉, 쿼리의 개수가 최대 5만 개이므로 각 쿼리를 시간복잡도 $O(logN)$으로 연산을 해야 한다. 따라서 우리는 세그먼트 트리 혹은 인덱스 트리를 생각할 수 있다. 

 

인덱스 트리를 사용해야 하는 것은 알았는데 인덱스 트리의 노드에 어떤 값을 저장해야 할까? 위에서 2번째 행동을 다시 보자. A번 선반부터 B번 선반까지 순서에 상관없이 A번 DVD부터 B번 DVD까지 모두 존재하는지 여부를 판단해야 한다. 순서에 상관없이 A번부터 B번까지 존재하는지 어떻게 판단할 수 있을까? 생각보다 쉽다. 바로 최솟값과 최댓값만 보면 되는 것이다. 

 

예를 들어 0번 선반부터 9번 선반까지 다음과 같이 DVD가 존재한다고 해보자. 

 

0

1

2

9

7

4

5

6

8

3

 

위 상태에서 4번 선반부터 7번 선반까지 DVD를 보면, 최솟값이 4이고 최댓값이 7인 것을 알 수 있다. 실제로 4번 DVD부터 7번 DVD까지 순서대로 위치하지는 않지만 분명히 존재한다는 것을 확인할 수 있다. 

 

이처럼 인덱스 트리의 노드에 특정 구간에 대한 최솟값과 최댓값을 저장한다면, A번 DVD부터 B번 DVD까지 존재하는지를 빠르게 판단할 수 있다. 이 문제를 풀기 전에 간단하게 연습을 하고 싶으면 다음 문제를 먼저 풀어보는 것을 추천한다. 

[백준 2357번] 최솟값과 최댓값 : https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

 

구현을 해보자. 먼저 N이 최대 10만이므로 다음과 같이 인덱스 트리 배열을 설정할 수 있다.

 

int OFFSET = 131072;
vector<pair<int,int>>tree(OFFSET * 2);

 

각 노드에 최솟값과 최댓값을 모두 저장하기 위해 pair<int,int>형으로 선언하였다. 

 

 

다음과 같이 각 노드를 초기화하자. 

 

void init() {
	tree.assign(OFFSET * 2, { INT_MAX,INT_MIN });
	for (int i = 0; i < N; i++) tree[OFFSET + i] = { i,i };
	for (int i = OFFSET - 1; i > 0; i--) {
		tree[i].first = min(tree[2 * i].first, tree[2 * i + 1].first);
		tree[i].second = max(tree[2 * i].second, tree[2 * i + 1].second);
	}
}

 

각 노드의 첫 번째 원소에 최솟값, 두 번째 원소에 최댓값을 저장해야 하므로 초기화를 할 때는 첫 번째 원소에는 가장 큰 값, 두 번째 원소에는 가장 작은 값을 저장해야 한다. 그리고 0번 선반부터 N-1번 선반까지는 처음에 0번 DVD부터 N-1번 DVD까지 차례대로 존재하므로 k번 선반에는 최솟값과 최댓값이 모두 k로 저장하면 된다. 이렇게 저장을 했다면, 리프 노트부터 루트 노트까지 첫 번째 원소에는 자식 노드들의 최솟값 중 최솟값, 두 번째 원소에는 자식 노드들의 최댓값 중 최댓값을 저장하면 된다. 

 

 

update와 query 함수는 다음과 같다. 

 

void update(int A, int B) {
	A += OFFSET, B += OFFSET;
	swap(tree[A], tree[B]);
	while (A > 1) {
		A /= 2;
		tree[A].first = min(tree[2 * A].first, tree[2 * A + 1].first);
		tree[A].second = max(tree[2 * A].second, tree[2 * A + 1].second);
	}
	while (B > 1) {
		B /= 2;
		tree[B].first = min(tree[2 * B].first, tree[2 * B + 1].first);
		tree[B].second = max(tree[2 * B].second, tree[2 * B + 1].second);
	}
}
void query(int A, int B) {
	int minDVD = INT_MAX, maxDVD = INT_MIN;
	int a = A + OFFSET, b = B + OFFSET;
	while (a <= b) {
		if (a % 2 == 1) {
			minDVD = min(minDVD, tree[a].first);
			maxDVD = max(maxDVD, tree[a].second);
			a++;
		}
		if (b % 2 == 0) {
			minDVD = min(minDVD, tree[b].first);
			maxDVD = max(maxDVD, tree[b].second);
			b--;
		}
		a /= 2, b /= 2;
	}
	if (minDVD == A && maxDVD == B) cout << "YES\n";
	else cout << "NO\n";
}

 

update 함수에서 swap 함수를 이용하여 A번 선반의 DVD와 B번 선반의 DVD를 바꾼 후, 루트 노드까지 값을 갱신하였다. 

query 함수는 기존 구간 합을 구하는 것처럼 A번 선반부터 B번 선반까지의 최솟값과 최댓값을 구한 후, 최솟값이 A와 같고 최댓값이 B와 같으면 YES, 같지 않으면 NO를 출력하도록 하였다. 

---

3. 전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <climits>
#include <cmath>
#define INF INT_MAX
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int N, K;
int OFFSET = 131072;
vector<ii>tree(OFFSET * 2);
void init() {
	tree.assign(OFFSET * 2, { INT_MAX,INT_MIN });
	for (int i = 0; i < N; i++) tree[OFFSET + i] = { i,i };
	for (int i = OFFSET - 1; i > 0; i--) {
		tree[i].first = min(tree[2 * i].first, tree[2 * i + 1].first);
		tree[i].second = max(tree[2 * i].second, tree[2 * i + 1].second);
	}
}
void update(int A, int B) {
	A += OFFSET, B += OFFSET;
	swap(tree[A], tree[B]);
	while (A > 1) {
		A /= 2;
		tree[A].first = min(tree[2 * A].first, tree[2 * A + 1].first);
		tree[A].second = max(tree[2 * A].second, tree[2 * A + 1].second);
	}
	while (B > 1) {
		B /= 2;
		tree[B].first = min(tree[2 * B].first, tree[2 * B + 1].first);
		tree[B].second = max(tree[2 * B].second, tree[2 * B + 1].second);
	}
}
void query(int A, int B) {
	int minDVD = INT_MAX, maxDVD = INT_MIN;
	int a = A + OFFSET, b = B + OFFSET;
	while (a <= b) {
		if (a % 2 == 1) {
			minDVD = min(minDVD, tree[a].first);
			maxDVD = max(maxDVD, tree[a].second);
			a++;
		}
		if (b % 2 == 0) {
			minDVD = min(minDVD, tree[b].first);
			maxDVD = max(maxDVD, tree[b].second);
			b--;
		}
		a /= 2, b /= 2;
	}
	if (minDVD == A && maxDVD == B) cout << "YES\n";
	else cout << "NO\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		cin >> N >> K;
		init();
		while (K--) {
			int Q, A, B; cin >> Q >> A >> B;
			if (Q == 0) update(A, B);
			else query(A, B);
		}
	}
	return 0;
}