디지털 비디오 디스크

문제 링크

풀이

연속하는 구간에 순서에 무관하게 그 구간 번호에 해당하는 수가 들어가있어야 한다. 4~6번 구간에 대한 쿼리가 들어왔을 때, 4 5 6, 5 4 6, 6 5 4 등등의 배열이 모두 가능하지만 반드시 4, 5, 6이 모두 들어있어야 한다. 수열에 중복되는 수는 없기 때문에 비둘기집 원리에 의해 구간의 최댓값 최솟값 2가지만 일치하면 조건을 만족한다고 볼 수 있다. 또한 현재 DVD 선반의 상태도 알아야 하기 때문에 처음에 입력받은 배열에서 실제로 값을 바꿔가며 현재 DVD 선반의 상태도 알 수 있는 상태로 유지하는 것이 코드를 작성하기 편리하다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
struct node {
    ll mn = (ll)9e18, mx = (ll)-9e18;
};
int n, m;
vector<ll> arr;
vector<node> seg;
// n : tree 기준 노드 번호
// s : 배열 구간 시작 인덱스
// e : 배열 구간 종료 종료 인덱스
node init(int n, int s, int e) {
    if (s == e) { // 시작 인덱스와 종료 인덱스가 같다면 리프 노드이므로 배열값 반환
        return seg[n] = { arr[s], arr[s] };
    }
    int mid = (s + e) / 2;
    node s1 = init(n * 2, s, mid); // 왼자식 탐색
    node s2 = init(n * 2 + 1, mid + 1, e); // 오른자식 탐색
    return seg[n] = { s1.mn < s2.mn ? s1.mn : s2.mn, s1.mx > s2.mx ? s1.mx : s2.mx }; // 양쪽 자식 최대 / 최소값 비교 후 더 나은 쪽 리턴
}
// n : tree 기준 노드 번호
// t : 값을 변경할 인덱스
// r : 업데이트 값
// s : 배열 구간 시작 인덱스
// e : 배열 구간 종료 종료 인덱스 
node update(int n, int t, int p, int s, int e) {
    if (t < s || t > e) return seg[n];
    if (s == e) {
        return seg[n] = { p, p };
    }
    int mid = (s + e) / 2;
    node s1 = update(n * 2, t, p, s, mid);
    node s2 = update(n * 2 + 1, t, p, mid + 1, e);
    return seg[n] = { s1.mn < s2.mn ? s1.mn : s2.mn, s1.mx > s2.mx ? s1.mx : s2.mx };
}
// n : tree 기준 노드 번호
// l : 합을 구하는 구간 시작 인덱스
// r : 합을 구하는 구간 종료 인덱스
// s : 배열 구간 시작 인덱스
// e : 배열 구간 종료 종료 인덱스 
node getmnmx(int n, int l, int r, int s, int e) {
    if (l <= s && e <= r) return seg[n]; // 구간을 완전히 포함하는 경우, 노드 값 반환
    if (r < s || e < l) return { (ll)9e18, (ll)-9e18 }; // 구간이 전혀 포함되지 않는 경우, 최대 최소 쓰레기값 반환 ( 9e18, -9e18 )
    int mid = (s + e) / 2;
    node s1 = getmnmx(n * 2, l, r, s, mid); // 왼자식 탐색 
    node s2 = getmnmx(n * 2 + 1, l, r, mid + 1, e); // 오른자식 탐색
    return { s1.mn < s2.mn ? s1.mn : s2.mn, s1.mx > s2.mx ? s1.mx : s2.mx }; // 양쪽 자식 최대 / 최소값 비교 후 더 나은 쪽 리턴
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m; arr = vector<ll>(n + 1); seg = vector<node>((int)pow(2, (int)ceil(log2(n)) + 1));
        for (int i = 1; i <= n; i++) {
            arr[i] = i;
        }
        init(1, 1, n);
        for (int i = 1; i <= m; i++) {
            int q, s, e; cin >> q >> s >> e; s++; e++;
            if (q == 0) {
                update(1, s, arr[e], 1, n);
                update(1, e, arr[s], 1, n);
                ll t = arr[s]; arr[s] = arr[e]; arr[e] = t;
            }
            else {
                node ret = getmnmx(1, s, e, 1, n);
                cout << (ret.mn == s && ret.mx == e ? "YES" : "NO") << "\n";
            }
        }        
    }
    return 0;
}