[ BOJ ] 9345 : 디지털 비디오 디스크(DVDs) ( PLATINUM 3 ) / C

문제

최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DVD들로 구성된 시리즈를 구매한다(각 DVD들은 0번부터 N-1 까지 이루어져 있다).

ACM 대여점의 주인 원주연 또한 울며 겨자먹기로 인기있는 시리즈물을 구매했고, 진열을 하기 위해 맞춤형 선반을 주문제작 하였다(맟춤제작이기 때문에 선반의 번호 또한 0번부터 N-1 까지 이루어져 있다). 주연이는 매우 정갈한 사람이기 때문에 DVD를 진열할 때 i번 DVD는 i번 선반에 진열을 한다.

이 시리즈의 열렬한 팬인 민호는 주연이네 대여점에 시리즈가 입고되었다는 소식을 듣고 찾아왔다. 시리즈물은 연속으로 봐야 흥미가 안떨어지기 때문에 민호는 L번부터 R번까지의 DVD들을 빌리려고 한다. 민호는 주연이가 매우 정갈한 성격인 것임을 알기에 주연이를 믿고 실제 DVD들의 번호를 확인하지 않고 L번 선반부터 R번 선반까지 존재하는 DVD들을 들고 카운터에 가져왔다.

그러나, 민호는 간과한 사실이 있다. 주연이네 대여점에는 진상 손님인 진일이가 찾아온다는 것이였다. 진일이는 선반 A 에 있는 DVD와 선반 B에 있는 DVD를 서로 바꿔 놓는다. 이러한 진일이의 몰상식한 행동때문에 민호와 같이 주연이를 믿고 DVD의 번호를 확인 안하는 선량한 고객들이 피해를 입는 사례들이 속출하였다. 아무 이유가 없는 묻지마 테러로 인해 가게매출이 떨어질 위기에 처하자 주연이는 진일이가 보일때마다 쫒아 냈지만, 시도때도없이 찾아오는 진일이의 진상짓을 막기에는 역부족이였다.

이러한 주연이를 보고 안타까운 마음이 든 민호는 주연이를 위해 프로그램을 작성하기로 결심을 한다. 의욕이 넘치는 민호의 마음과는 달리 실력이 따라주지 못해 프로그램의 기능은 조촐하기만 하다. 프로그램의 기능은 다음과 같다.

1. 손님이 L번 선반부터 R번 선반까지에 있는 DVD들을 가져 왔을때 실제로 DVD가 L번부터 R번까지 있나 확인을 해 줄 수 있다.
2. DVD의 순서는 상관이 없다. 예를 들어 손님이 2번 선반부터 4번 선반까지에 있는 DVD를 가져왔을 때 DVD가 2, 3, 4 순서로 진열되어 있건, 4, 2, 3 순서로 진열되어 있건 상관이 없다는 얘기다. 즉 L번부터 R번까지의 DVD가 있으면 된다.

문제의 단순화를위해 고객이 DVD를 빌려가면, 그 즉시 시청한뒤 바로 반납한다고 가정한다. 또한 가져다 놓는 위치는 빌리기 전과 동일하다(4, 3, 2 순서로 진열되어 있었으면 다시 4, 3, 2 순서로 진열한다).

입력

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. (T ≤ 20 인 자연수)

각각의 테스트 케이스 첫 번째 줄에는 DVD들의 수를 의미하는 정수 N 과 대여점에서 일어나는 사건의 수를 의미하는 정수 K 가 주어진다. (1 ≤ N ≤ 100,000 , 1 ≤ K ≤ 50,000)

이어서 대여점에서 일어나는 사건 K 개가 주어진다. 각각의 줄은 세 정수 Q, A, B 을 포함한다. (Q는 0또는 1이고, 0 ≤ A ≤ B < N )

Q는 0 일때, 진상 손님 진일이가 선반 A의 DVD와 선반 B의 DVD를 서로 바꿔 끼우는 사건을 의미한다. 

Q가 1 일때는 손님이 선반 A부터 선반 B에 있는 DVD를 카운터에 가져오는 사건을 의미한다. 위에서도 언급했듯이 이 사건이 DVD들의 위치를 바꾸는 일은 일어나지 않는다.

출력

손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하고, 그렇지 않다면 "NO"를 출력한다.

풀이 과정

최댓값 최솟값 세그먼트 트리를 만들고, 해당 구간의 최솟값과 최댓값이 A번과 B번과 일치하다면 그 안에 DVD가 전부 있는 것으로 판정한다..

#include <stdio.h>
#define SIZE 100001

int arr[SIZE];
int tree[SIZE * 4][2]; // min, max

void init(int start, int end, int idx) {
	if (start == end) {
		tree[idx][0] = start;
		tree[idx][1] = start;
		arr[start] = start;
		return;
	}
	int mid = (start + end) / 2;
	init(start, mid, idx * 2);
	init(mid + 1, end, idx * 2 + 1);
	tree[idx][0] = (tree[idx * 2][0] < tree[idx * 2 + 1][0]) ? tree[idx * 2][0] : tree[idx * 2 + 1][0];
	tree[idx][1] = (tree[idx * 2][1] > tree[idx * 2 + 1][1]) ? tree[idx * 2][1] : tree[idx * 2 + 1][1];
}

int getBook(int start, int end, int idx, int what) {
	if (what < start || end < what) return -1;
	if (start == end) return arr[start];

	int mid = (start + end) / 2;
	int q1 = getBook(start, mid, idx * 2, what);
	int q2 = getBook(mid + 1, end, idx * 2 + 1, what);

	if (q1 == -1 && q2 == -1) return -1;
	else if (q1 != -1) return q1;
	else return q2;
}

void putBook(int start, int end, int idx, int what, int value) {
	if (what < start || end < what) return;
	if (start == end) {
		tree[idx][0] = value;
		tree[idx][1] = value;
		arr[start] = value;
		return;
	}

	int mid = (start + end) / 2;
	putBook(start, mid, idx * 2, what, value);
	putBook(mid + 1, end, idx * 2 + 1, what, value);
	tree[idx][0] = (tree[idx * 2][0] < tree[idx * 2 + 1][0]) ? tree[idx * 2][0] : tree[idx * 2 + 1][0];
	tree[idx][1] = (tree[idx * 2][1] > tree[idx * 2 + 1][1]) ? tree[idx * 2][1] : tree[idx * 2 + 1][1];
}

int interval_min(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return -1;
	if (left <= start && end <= right) return tree[idx][0];

	int mid = (start + end) / 2;
	int q1 = interval_min(start, mid, idx * 2, left, right);
	int q2 = interval_min(mid + 1, end, idx * 2 + 1, left, right);
	if (q1 == -1 && q2 == -1) return -1;
	else if (q1 != -1 && q2 != -1) return (q1 < q2) ? q1 : q2;
	else if (q1 != -1) return q1;
	else return q2;
}

int interval_max(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return -1;
	if (left <= start && end <= right) return tree[idx][1];

	int mid = (start + end) / 2;
	int q1 = interval_max(start, mid, idx * 2, left, right);
	int q2 = interval_max(mid + 1, end, idx * 2 + 1, left, right);
	if (q1 == -1 && q2 == -1) return -1;
	else if (q1 != -1 && q2 != -1) return (q1 > q2) ? q1 : q2;
	else if (q1 != -1) return q1;
	else return q2;
}

int main(void) {
	int test;
	scanf("%d", &test);
	while (test--) {
		int n, k;
		scanf("%d %d", &n, &k);
		init(0, n - 1, 1);

		for (int i = 0; i < k; i++) {
			int q, a, b;
			scanf("%d %d %d", &q, &a, &b);

			if (q == 0) {
				int tmp1 = getBook(0, n - 1, 1, a);
				int tmp2 = getBook(0, n - 1, 1, b);
				putBook(0, n - 1, 1, a, tmp2);
				putBook(0, n - 1, 1, b, tmp1);
			}
			else {
				int mins = interval_min(0, n - 1, 1, a, b);
				int maxs = interval_max(0, n - 1, 1, a, b);
				// printf("%d %d / %d %d\n", mins, a, maxs, b);
				if (mins == a && maxs == b) printf("YES\n");
				else printf("NO\n");
			}
		}
	}
	return 0;
}