백준[9345] 디지털 비디오 디스크(DVDs)

문제 설명

문제 링크

http://icpc.me/9345

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

풀이

세그먼트 트리를 이용하여 풀이할 수 있다.

a ~ b 사이에 a, a+1, ... , b 만 존재한다면 이때 최솟값은 a 최댓값은 b이다. 만약 저 구간에 다른 값이 들어간다면 최솟값, 최댓값은 a, b가 될 수 없다.

이 구간 최대, 최소값을 세그먼트 트리로 관리하면 쿼리당 O(logN)에 처리할 수 있다. 

코드

#include <cstdio>
#include <algorithm>

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

pii tree[400005];
int loc[100005];

pii init(int node, int s, int e) {
    if (s == e) return tree[node] = {s, s};
    int mid = (s + e) >> 1;
    pii left = init(2 * node, s, mid);
    pii right = init(2 * node + 1, mid + 1, e);
    return tree[node] = {min(left.first, right.first), max(left.second, right.second)};
}

pii query(int node, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return {1e9, -1e9};
    if (qs <= s && e <= qe) return tree[node];
    int mid = (s + e) >> 1;
    pii left = query(2 * node, s, mid, qs, qe);
    pii right = query(2 * node + 1, mid + 1, e, qs, qe);
    return {min(left.first, right.first), max(left.second, right.second)};
}

pii update(int node, int s, int e, int idx, int num) {
    if (idx < s || idx > e) return tree[node];
    if (s == e) return tree[node] = {num, num};
    int mid = (s + e) >> 1;
    pii left = update(2 * node, s, mid, idx, num);
    pii right = update(2 * node + 1, mid + 1, e, idx, num);
    return tree[node] = {min(left.first, right.first), max(left.second, right.second)};
}

void solve() {
    int n, k; scanf("%d %d", &n, &k);
    init(1, 0, n - 1);
    for (int i = 0; i < n; i++) loc[i] = i;
    while (k--) {
        int q, a, b; scanf("%d %d %d", &q, &a, &b);
        if (!q) {
            update(1, 0, n - 1, loc[a], b);
            update(1, 0, n - 1, loc[b], a);
            swap(loc[a], loc[b]);
        } else {
            auto [m, M] = query(1, 0, n - 1, a, b);
            if (a == m && b == M) printf("YES\n");
            else printf("NO\n");
        }
    }
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        solve();
    }
}