BOJ 9345 디지털 비디오 디스크(DVDs)

1 개요

BOJ 9345 디지털 비디오 디스크(DVDs)

• 백준 온라인 저지 9345번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int min_val, max_val;
    long long int value;
    Node() : min_val(0), max_val(0), value(0) {}
    Node(int min_val, int max_val, long long int value) : min_val(min_val), max_val(max_val), value(value) {}
};

class SegmentTree {
public:
    SegmentTree(int n) : size(n) {
        int tree_size = 1 << (int)ceil(log2(n) + 1);
        tree.resize(tree_size);
        build(1, 0, size - 1);
    }

    void build(int cur, int left, int right) {
        if (left == right) {
            tree[cur] = Node(left, left, left);
            return;
        }
        int mid = (left + right) / 2;
        build(2 * cur, left, mid);
        build(2 * cur + 1, mid + 1, right);
        tree[cur] = combine(tree[2 * cur], tree[2 * cur + 1]);
    }

    Node combine(const Node& left, const Node& right) {
        return Node(min(left.min_val, right.min_val), max(left.max_val, right.max_val), left.value + right.value);
    }

    void update(int cur, int left, int right, int idx, int val) {
        if (left == right) {
            tree[cur] = Node(val, val, val);
            return;
        }
        int mid = (left + right) / 2;
        if (idx <= mid) {
            update(2 * cur, left, mid, idx, val);
        } else {
            update(2 * cur + 1, mid + 1, right, idx, val);
        }
        tree[cur] = combine(tree[2 * cur], tree[2 * cur + 1]);
    }

    Node query(int cur, int left, int right, int q_left, int q_right) {
        if (q_right < left || right < q_left) {
            return Node(INT_MAX, INT_MIN, 0);
        }
        if (q_left <= left && right <= q_right) {
            return tree[cur];
        }
        int mid = (left + right) / 2;
        Node left_result = query(2 * cur, left, mid, q_left, q_right);
        Node right_result = query(2 * cur + 1, mid + 1, right, q_left, q_right);
        return combine(left_result, right_result);
    }

private:
    vector<Node> tree;
    int size;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        SegmentTree st(N);
        vector<int> loc(N);
        for (int i = 0; i < N; ++i) {
            loc[i] = i;
        }
        int a, b, c;
        while (K--) {
            cin >> a >> b >> c;
            if (a == 0) {
                st.update(1, 0, N - 1, loc[b], c);
                st.update(1, 0, N - 1, loc[c], b);
                swap(loc[b], loc[c]);
            } else {
                Node result = st.query(1, 0, N - 1, b, c);
                if (b == result.min_val && c == result.max_val) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }
}