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

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

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

 

 

풀이

[L, R] 범위에 책이 모두 있는지 확인하는 방법은 첫 번째로 머지 소트 트리를 통하여 DVD가 L부터 R까지 있는지 확인해볼 수 있습니다.

머지 소트 트리가 정렬된 DVD 번호를 가져오니까 만약 [L, R]이 입력 값으로 들어온다면 [L, L+1, L+2, ... , R-1, R]로 들어오겠네요.

 

여기서 좀 더 생각해보면 우리가 머지 소트 트리를 사용하는 이유는 맨 왼쪽값이 L인지, 맨 오른쪽 값이 R인지 확인해보려고 만든 것입니다. 이걸 다르게 말하면 최솟값이 L인지, 최댓값이 R인지 확인만 하면 된다는 것이죠.

만약 폐구간 [L, R] 범위안에 있는 값 K대신 폐구간에 해당하지 않는 다른 값 x가 들어간다고 가정해봅시다. 이때 x > R이라면 [L +1, L+2, .., K-1, K+1, ... , R -1, R, x]로 맨 오른쪽 값이 x가 되어 답이 아니게 됩니다. 다르게 말하면 최댓값이 R이 아니게 되는 것이죠.

 

그래서 최솟값을 찾는 세그먼트트리, 최댓값을 찾는 세그먼트트리를 이용하여 최솟값이 L인지, 최댓값이 R인지 확인해주면 됩니다.

 

 

코드

#include <iostream>
using namespace std;
typedef long long ll;
 
const int N = 1e5 + 1;
int n, m, t;
int arr[N], min_tree[4 * N], max_tree[4 * N];
 
 int min_update(int now, int s, int e, int idx, int val) {
    if (s > idx || e < idx) return min_tree[now];
    if (s == e) return min_tree[now] = val;
    int mid = (s + e) / 2;
    return min_tree[now] = min(min_update(now * 2, s, mid, idx, val), min_update(now * 2 + 1, mid + 1, e, idx, val));
 }
 
int max_update(int now, int s, int e, int idx, int val) {
    if (s > idx || e < idx) return max_tree[now];
    if (s == e) return max_tree[now] = val;
    int mid = (s + e) / 2;
    return max_tree[now] = max(max_update(now * 2, s, mid, idx, val), max_update(now * 2 + 1, mid + 1, e, idx, val));
}
 
int find_min(int now, int s, int e, int L, int R) {
    if (R<s || L>e) return 987654321;
    if (L <= s && e <= R) return min_tree[now];
    int mid = (s + e) / 2;
    return min(find_min(now * 2, s, mid, L, R), find_min(now * 2 + 1, mid + 1, e, L, R));
}
 
int find_max(int now, int s, int e, int L, int R) {
    if (R<s || L>e) return 0;
    if (L <= s && e <= R) return max_tree[now];
    int mid = (s + e) / 2;
    return max(find_max(now * 2, s, mid, L, R), find_max(now * 2 + 1, mid + 1, e, L, R));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t--) {
        cin >> n >> m;
 
        for (int i = 0; i < n; i++) {
            arr[i] = i;
            min_update(1, 0, n - 1, i, i);
            max_update(1, 0, n - 1, i, i);
        }
 
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            if (a == 0) {
                min_update(1, 0, n - 1, b, arr[c]);
                max_update(1, 0, n - 1, b, arr[c]);
                min_update(1, 0, n - 1, c, arr[b]);
                max_update(1, 0, n - 1, c, arr[b]);
                int x = arr[b];
                arr[b] = arr[c];
                arr[c] = x;
            }
            else {
                int x = find_min(1, 0, n - 1, b, c);
                int y = find_max(1, 0, n - 1, b, c);
                if (x == b && y == c) cout << "YES" << '\n';
                else cout << "NO" << '\n';
            }
        }
    }
}