boj 9345 - 디지털 비디오 디스크(DVDs)

boj 9345

 

목차

개요

설명

코드

---

개요

boj 9345 - 디지털 비디오 디스크(DVDs) 문제도 segment tree를 응용한 문제입니다.

 

Query 0 이 들어왔을 때는 DVD 배열에서 a번째와 b번째의 값을 바꿔주면 되고, Query 1이 들어왔을 때는 a ~ b 의 구간을 검색하면 됩니다.

 

얼핏 보기에는 segment tree를 어떻게 응용해야 하는 지에 대해 의문이 들 수 있습니다. 하지만 잘 살펴보면, Query 1이 들어왔을 때는 "a ~ b 의 구간에서 DVD가 a번부터 b번까지 모두 존재하는가" 를 살펴 보면 됩니다.

 

문제를 바꾸면, a ~ b 구간에서 중간 DVD를 살펴 볼 필요 없이 최솟값과 최댓값을 살펴보면 됩니다.

즉, a ~ b 구간의 최솟값이 a이면서, 최댓값이 b라면 조건을 만족하게 되는 것이죠.

 

이 문제는 [boj2357 - 최솟값과 최댓값]와 크게 다르지 않습니다. 다만, Update 함수를 구현해야 한다는 차이가 있습니다..

---

설명

boj 9345에서

5 5
0 1 2
0 2 3
0 1 3
1 0 1
1 0 2

예제를 한 번 살펴보겠습니다.

 

최댓값 segment tree를 살펴보면 아래와 같이 그릴 수 있겠죠.

문제에서 DVD들은 처음에 0번부터 순서대로 잘 나열되어 있었다고 하니, 초기 값들은 0, 1, 2, 3, 4 이렇게 넣어주면 됩니다.

 

Step 1 : query 0 1 2

이제 0 1 2 를 수행해봅시다. 먼저 swap을 위해서는 각 배열의 값이 무엇인지를 알아야 합니다. 지금은 쉽게 1번에 1이 저장되어 있고, 2번에 2가 저장되어 있습니다. 이들을 임시 변수에 저장했다가 swap하면 됩니다.

그 결과 아래와 같이 maximum tree가 재구성 되겠지요.

 

Step 2 : query 0 2 3

다음은 0 2 3 입니다. 2번 index와 3 번 index를 바꿔줘야 합니다.

당연하지만 신경써야 할 부분은, 이제 더 이상 arr[2]에 2가 들어 있지 않습니다. 1이 들어있지요. 따라서 이 문제에서는 Update에 앞서 arr[a]와 arr[b]에 어떤 값이 들어있는지를 먼저 안 뒤에, 그 값들을 잠시 저장해 놓아야 합니다.

 

Step 3 : query 0 1 3

update query중에 마지막으로 0 1 3입니다.

마찬가지로 1번과 3번에 어떤 값이 있는지 검색한 다음에 그 값들을 바꿔주면 됩니다.

 

Step 4 : query 1 0 1

이제는 검색 query입니다. Step 1 ~ Step 3 을 통해서 아마 다음과 같이 최소 최대 segment tree가 구성되어 있을 것입니다.

query 1 0 1 은 최소 최대 segment tree 각각에 대하여 0 ~ 1 범위의 값을 구하면 됩니다. 이는 각각 4번 index에 해당해서 최소 segment tree에서는 0, 최대 segment tree에서는 1을 얻을 수 있습니다.

 

이제 이 값들을 기존의 query 0과 1을 비교하면 됩니다. 0==0 && 1==1 이므로 "YES"가 되겠죠.

 

Step 5 : query 1 0 2

query 1 0 2 는 각 세그먼트 트리에서 2번 index와 같습니다. 최소 tree에서는 0, 최대 tree에서는 3이 나오네요. 마찬가지로 비교하면 되는데, 0==0 && 2==3 은 거짓이므로 "NO"가 됩니다.

---

Code

1. boj 2357과 마찬가지로 하나의 class로 구현하되, 함수 포인터를 사용하여 최소 최대 tree를 구분할 수 있도록 하였습니다.

※주의할점

2. Query 0번을 수행할 때, a와 b에 단순히 b값과 a값을 넣는 것이 아닌, arr[b]와 arr[a]를 넣어야 합니다. 이 코드에서는 DVD가 swap되고 난 뒤의 정보를 arr에 계속 저장합니다.
3. 하나의 Testcase가 아니라 여러 개의 Testcase를 수행합니다. 따라서 매 testcase마다 배열, tree, 변수 등의 자료구조 초기화에 유의해야 합니다.

#include<stdio.h>
#define INTMAX 100001
#define INTMIN -1
using namespace std;

int arr[100000];

int min(int a, int b){
        return a>b? b:a;
}
int max(int a, int b){
        return a>b? a:b;
}
class Tree{
        int node[400000];

        public:

        int Init(int cur, int left, int right, int (*func)(int,int)){
                if(left==right){
                        return node[cur] = arr[left];
                }
                int mid = (left+right)/2;
                return node[cur] = func(Init(cur*2, left, mid, func), Init(cur*2+1, mid+1, right, func));
        }

        int Search(int cur, int left, int right, int start, int end, int (*func)(int,int)){
                if(start >= left && end <= right){
                        return node[cur];
                }
                int mid = (start+end)/2;
                int ret1 = -1, ret2 = -1;
                if(left<=mid) ret1 = Search(cur*2, left, right, start, mid, func);
                if(right>mid) ret2 = Search(cur*2+1, left, right, mid+1, end, func);

                if(ret1 == -1) return ret2;
                else if(ret2 == -1) return ret1;
                else return func(ret1, ret2);
        }

        void Update(int cur, int left, int right, int index, int value, int (*func)(int,int)){
                if(left==right){
                        node[cur] = value;
                        return;
                }
                int mid = (left+right)/2;
                // 하나의 index만 update를 요하므로, mid를 기준으로 왼쪽 오른쪽 중 하나만 선택하여 재귀
                if(index <= mid) Update(cur*2, left, mid, index, value, func);
                if(index > mid) Update(cur*2+1, mid+1, right, index, value, func);

                // child node가 update를 끝냈으면, 자신의 node도 child node의 값들을 이용하여 갱신해야함.
                node[cur] = func(node[cur*2], node[cur*2+1]);
        }
};

int main(){
        int Testcase;
        scanf("%d",&Testcase);
        while(Testcase--){
                int N,K;
                scanf("%d %d",&N,&K);

                for(int i=0;i<N;i++){
                        arr[i] = i;
                }

                Tree* t_min = new Tree();
                Tree* t_max = new Tree();

                t_min->Init(1, 0, N-1, min);
                t_max->Init(1, 0, N-1, max);

                int q,a,b;
                for(int i=0;i<K;i++){
                        scanf("%d %d %d",&q,&a,&b);
                        if(q==0){
                                t_min->Update(1, 0, N-1, a, arr[b], min);
                                t_min->Update(1, 0, N-1, b, arr[a], min);
                                t_max->Update(1, 0, N-1, a, arr[b], max);
                                t_max->Update(1, 0, N-1, b, arr[a], max);

                                //a번째와 b번째의 DVD가 바뀔 때, arr 배열에 현재 index의 DVD 정보를 유지
                                int tmp = arr[a];
                                arr[a] = arr[b];
                                arr[b] = tmp;
                        }else{
                                int ret_min = t_min->Search(1, a, b, 0, N-1, min);
                                int ret_max = t_max->Search(1, a, b, 0, N-1, max);

                                if(ret_min==a && ret_max==b) printf("YES\n");
                                else printf("NO\n");
                        }
                }
        }
}