[ICPC] 백준 9345 - 디지털 비디오 디스크

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

 

아이디어

고객이 l번부터 r번까지의 DVD를 원할 때 이들의 index 최솟값과 최댓값은 l과 r이다.

 

그러면 도중에 DVD가 바뀌었다 하더라도 l번부터 r번까지 DVD의 index 최솟값과 최댓값이 l과 r이면 해당 구간에 동일한 내용물이 들어있음을 이해할 수 있다.

 

왜냐하면 DVD 집합의 크기가 변하는 것이 아니기 때문에 index의 경계를 살펴보면 원하는 원소들이 속해있는지 속하지 않았는지 판단할 수 있기 때문이다.

 

그러면 세그먼트 트리를 통해 특정 구간에서 index의 최소와 최대를 저장하여 질의를 처리하는 방법을 생각해 볼 수 있다.

구현

문제를 풀기 위해 다음 역할을 하는 배열을 사용한다.

 

ar[선반 번호] = DVD 번호

 

초기에는 선반 번호와 해당 선반에 비치된 DVD의 번호가 같으므로 배열의 각 index에 동일한 숫자를 가지도록 초기화 한다.

 

세그먼트 트리가 구간에서 index의 최솟값과 최댓값을 저장할 수 있는 자료구조를 가지도록 한다. 작성자는 pair로 간단하게 구현했다.

 

세그먼트 트리를 통해 특정 구간에서 index의 최소와 최대를 찾을 수 있도록 함수를 작성한 후 문제에 요구에 맞는 질의를 처리하면 된다. 작성 방법은 밑에 첨부한 코드를 참고하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int t;
int ar[100000];

inline int mid(int s, int e) { return s + (e - s) / 2; }

pii init(vector<pii> &tree, int node, int start, int end)
{
    if (start == end) return tree[node] = {start, end};
    int m = mid(start, end);

    init(tree, node * 2, start, m);
    init(tree, node * 2 + 1, m + 1, end);

    tree[node].first = min(tree[node * 2].first, tree[node * 2 + 1].first);
    tree[node].second = max(tree[node * 2].second, tree[node * 2 + 1].second);
    return tree[node];
}

pii update(vector<pii> &tree, int node, int start, int end, int idx)
{
    if (idx < start || idx > end) return tree[node];

    if (start == end)
    {
        tree[node].first = tree[node].second = ar[idx];
        return tree[node];
    }

    int m = mid(start, end);

    pii l = update(tree, node * 2, start, m, idx);
    pii r = update(tree, node * 2 + 1, m + 1, end, idx);

    tree[node].first = min(l.first, r.first);
    tree[node].second = max(l.second, r.second);

    return tree[node];
}

pii query(vector<pii> &tree, int node, int start, int end, int l, int r)
{
    if (start > r || end < l) return {1e9, -1e9};
    if (l <= start && end <= r) return tree[node];

    int m = mid(start, end);
    pii l_node = query(tree, node * 2, start, m, l, r);
    pii r_node = query(tree, node * 2 + 1, m + 1, end, l, r);

    pii ret;
    ret.first = min(l_node.first, r_node.first);
    ret.second = max(l_node.second, r_node.second);
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;

    while (t--)
    {
        int n, k;
        cin >> n >> k;

        vector<pii> segtree(n * 4);
        init(segtree, 1, 0, n - 1);

        for (int i = 0; i < n; ++i)
            ar[i] = i;

        while (k--)
        {
            int q, a, b;
            cin >> q >> a >> b;

            if (!q)
            {
                if (a == b)
                    continue;
                
                swap(ar[a], ar[b]);
                update(segtree, 1, 0, n - 1, a);
                update(segtree, 1, 0, n - 1, b);
            }
            else
            {
                pii res = query(segtree, 1, 0, n - 1, a, b);
                if (res.first == a && res.second == b)
                    cout << "YES\n";
                else
                    cout << "NO\n";
            }
        }
    }
}