boj,백준) 9345. 디지털 비디오 디스크(DVDs) ( C++)

1. 문제 링크

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

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

2. 문제 개요

N개의 DVD가 0번부터 N-1번까지 정리되어 있다.

그런데 나쁜 손님이 와서 A번 DVD과 B번 DVD의 위치를 바꾼다.

착한 손님이 L번부터 R번까지의 DVD를 빌리려고 할 때, DVD를 자세히 보지 않고 L번째부터 R번째까지 그냥 통째로 가져간다.

이때, [L, R] 범위에 진짜 L~R번의 DVD가 모두 포함되어 있는지 체크하는 프로그램을 작성하자. 

 

3. 문제 힌트

테스트 케이스가 20개, 사건의 수 최대 5만 개.

각 쿼리는 두 DVD의 위치를 바꾸는 것과 DVD가 모두 포함되어있는지 체크하는 것 2개

 

→ 총사건의 개수는 100만 개 즉 각 쿼리가 logn의 형태로 실행되어야 함을 의미한다.

 

그렇다면 세그먼트 트리를 사용해보자

어떻게 적용하면 좋을까

 

순서 상관없이 [L, R]만 존재하면 된다.. 그럼 적어도 최대 최솟값은 L과 R이 되어야 할 테고...

 

4. 문제 풀이

문제의 핵심 내용은 3번에서 다 설명한 것 같다.

순서 상관없이 [L, R] 범위의 값들이 존재하는지 체크하면 된다.

이는 세그먼트 트리가 최솟값과 최댓값을 갖고 올라가면 됨을 의미한다.

 

 

예를 들어서 

1, 2, 3, 4, 5, 6, 7이 있다고 해보자. 여기서 [2, 6]을 꺼내려고 한다. 여기서 [2, 6]은 책장의 2번째 칸에서 6번째 칸을 꺼냄을 의미한다. 

만약에 1,3이 바뀐다면 3, 2, 1, 4, 5, 6, 7이고 [2, 6] 번째 칸을 꺼낸다고 했을 때 최솟값은 1이 되기 때문에 NO를 출력하는 방식으로 하면 된다.

 

중요한 점은 이제 각 DVD의 위치를 저장해야 한다는 점이다.

현재 i번째 DVD가 책장의 몇 번째 칸에 꽂혀있는지 알아야 바꿀 때 문제가 없다.

이점만 유의해서 풀자.

 

 

5. 코드

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

struct Node {
	Node() {}
	Node(int min_, int max_, long long int val_) :minval(min_), maxval(max_), val(val_) {}
	int minval, maxval;
	long long int val;
};

class Segment_tree
{
public:
	Segment_tree(int tree_size) { tree.resize(tree_size); }

	Node init_tree(int cur, int start, int end, int left, int right)
	{
		if (start == end) {
			Node ret(start, start, start);
			return tree[cur] = ret;
		}


		int mid = (start + end) / 2;

		Node l_ret = init_tree(cur * 2, start, mid, left, right);
		Node r_ret = init_tree(cur * 2 + 1, mid + 1, end, left, right);
		Node ret(min(l_ret.minval, r_ret.minval), max(l_ret.maxval, r_ret.maxval), l_ret.val + r_ret.val);
		return tree[cur] = ret;
	}

	Node query_change(int cur, int start, int end, int target, int val)
	{
		if (target < start || end < target)
			return tree[cur];

		if (start == end)	//target
		{
			Node ret(val, val, val);
			return tree[cur] = ret;
		}
		int mid = (start + end) / 2;
		Node l_ret = query_change(cur * 2, start, mid, target, val);
		Node r_ret = query_change(cur * 2 + 1, mid + 1, end, target, val);

		Node ret(min(l_ret.minval, r_ret.minval), max(l_ret.maxval, r_ret.maxval), l_ret.val + r_ret.val);
		return tree[cur] = ret;
	}

	Node query_sum(int cur, int start, int end, int left, int right)
	{
		if (end < left || right < start) {
			Node ret(987654321, -987654321, 0);
			return ret;
		}

		if (left <= start && end <= right)
			return tree[cur];

		int mid = (start + end) / 2;
		Node l_ret = query_sum(cur * 2, start, mid, left, right);
		Node r_ret = query_sum(cur * 2 + 1, mid + 1, end, left, right);

		return Node(min(l_ret.minval, r_ret.minval), max(l_ret.maxval, r_ret.maxval), l_ret.val + r_ret.val);
	}

	vector<Node>tree;
};

int t;

int main()
{
	scanf("%d", &t);

	while (t--)
	{
		int n, k;
		scanf("%d %d", &n, &k);
		//0 ~ n-1
		int h = (int)ceil(log2(n));
		int tree_size = 1 << (h + 1);
		Segment_tree sgt(tree_size);
		sgt.init_tree(1, 0, n - 1, 0, n - 1);

		vector<int> loc(n);
		for (int i = 0; i < n; ++i)
			loc[i] = i;

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

			if (a == 0)
			{
				int temp = loc[c];
				sgt.query_change(1, 0, n - 1, loc[b], c);
				loc[c] = loc[b];
				sgt.query_change(1, 0, n - 1, temp, b);
				loc[b] = temp;
			}
			else
			{
				Node ret = sgt.query_sum(1, 0, n - 1, b, c);

				if (b == ret.minval && c == ret.maxval) {
					printf("YES\n");
				}
				else {
					printf("NO\n");
				}
			}
		}

	}

	return 0;
}

피곤할 때 풀어서 코드가 조금 엉망일지도..(구조체에 val값도 빼도 됩니다. 세그먼트 트리만들때 val값도 빼도 됩니다.)

세그먼트 트리 내부에서 반환할 때 그냥 바로 생성자만 던지면 되는데.... 등등..

 

6. 결과

 

댓글 지적 환영입니다!!