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

📝 문제 정보

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

🧐 관찰 및 접근

수열에서의 swap연산이 주어지고, 수열의 $L, R$ 범위가 주어졌을 때 해당 범위에 $L \leq x \leq R$의 모든 수가 있는지 묻는 문제이다.
합같은것으로는 저걸 구분할 수가 없다. $(3, 4)$나 $(2, 5)$나 같으니까.
아하, DVD들끼리 겹치지 않으므로 구간 최소/최댓값을 이용하면 되겠다.

💻 풀이

코드 (C++):

void solve(){
    int N, K; cin >> N >> K;
    vector<pii> a(N);
    rep(i, 0, N) a[i] = {i, i};
    SegmentTree ST(N, a);
    while(K--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 0){
            int aval = ST.query(a, a).first;
            int bval = ST.query(b, b).first;
            ST.set(a, bval);
            ST.set(b, aval);
        }
        else{
            pii res = ST.query(a, b);
            if(res.first == a && res.second == b) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}