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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 9345번 문제인 디지털 비디오 디스크(DVDs)이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/9345

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

이 문제는 주어진 두 index a부터 b까지 중에 a부터 b까지의 원소가 모두 있는지를 묻는 쿼리를 빠르게 처리해야하는 문제이다.

 

다행히 문제의 수열에는 서로 같은 DVD가 존재하지 않으므로, 주어진 구간에 a부터 b까지의 원소가 모두 있다는 것은 주어진 구간에 존재하는 원소의 최솟값이 a이고 최댓값이 b라는 것과 동치이다.

그러므로, 구간 최댓값, 구간 최솟값 계산과 갱신을 지원하는 세그먼트 트리(segment tree) 두개를 이용하면 문제를 간단히 풀 수 있다.

 

현재 index a와 index b에 어떤 번호의 DVD가 들어있는지 빠르게 접근하기 위해 DVD 번호를 index에 저장해둔 배열을 사용할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::max; using std::min;

int arr[100001];
int maxseg[262145];
int minseg[262145];

int maxinit(int L, int R, int sI) {
    if (L == R) maxseg[sI] = L;
    else maxseg[sI] = max(maxinit(L, (L + R) / 2, sI * 2), maxinit((L + R) / 2 + 1, R, sI * 2 + 1));
    return maxseg[sI];
}

void maxupdate(int L, int R, int qI, int val, int sI) {
    if (R < qI || qI < L) return;
    else if (L == R) maxseg[sI] = val;
    else {
        maxupdate(L, (L + R) / 2, qI, val, sI * 2);
        maxupdate((L + R) / 2 + 1, R, qI, val, sI * 2 + 1);
        maxseg[sI] = max(maxseg[sI * 2], maxseg[sI * 2 + 1]);
    }
}

int maxquery(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 0;
    if (qL <= L && R <= qR) return maxseg[sI];
    return max(maxquery(L, (L + R) / 2, qL, qR, sI * 2), maxquery((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int mininit(int L, int R, int sI) {
    if (L == R) minseg[sI] = L;
    else minseg[sI] = min(mininit(L, (L + R) / 2, sI * 2), mininit((L + R) / 2 + 1, R, sI * 2 + 1));
    return minseg[sI];
}

void minupdate(int L, int R, int qI, int val, int sI) {
    if (R < qI || qI < L) return;
    else if (L == R) minseg[sI] = val;
    else {
        minupdate(L, (L + R) / 2, qI, val, sI * 2);
        minupdate((L + R) / 2 + 1, R, qI, val, sI * 2 + 1);
        minseg[sI] = min(minseg[sI * 2], minseg[sI * 2 + 1]);
    }
}

int minquery(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 100001;
    if (qL <= L && R <= qR) return minseg[sI];
    return min(minquery(L, (L + R) / 2, qL, qR, sI * 2), minquery((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

void solve() {
    int N, K; cin >> N >> K;
    for (int i = 1;i <= N;i++) arr[i] = i;
    maxinit(1, N, 1);
    mininit(1, N, 1);
    for (int i = 0;i < K;i++) {
        int Q, A, B; cin >> Q >> A >> B; A++; B++;
        if (Q == 0) {
            int arrA = arr[A], arrB = arr[B];
            minupdate(1, N, A, arrB, 1);
            minupdate(1, N, B, arrA, 1);
            maxupdate(1, N, A, arrB, 1);
            maxupdate(1, N, B, arrA, 1);
            arr[A] = arrB, arr[B] = arrA;
        }
        else {
            if (maxquery(1, N, A, B, 1) == B && minquery(1, N, A, B, 1) == A) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T;
    for (int i = 0;i < T;i++) {
        solve();
    }
}