BOJ 9345 DVDs

닫힌 구간 [a, b] 범위 내부의 순서는 고려되지 않으므로 구간의 최소, 최대를 구해서 a, b와 비교하면 되겠다.

 

 

#include<bits/stdc++.h>

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

int arr[100001];
pii Tree[400005];

void upd(int l, int r, int node, int p, int v){
    if(p<l || r<p) return;
    if(l==r) {
        Tree[node]={v, v};
        return;
    }
       
    int mid=l+r>>1;
    upd(l, mid, 2*node, p, v), upd(mid+1, r, 2*node+1, p, v);
    Tree[node]= { min(Tree[2*node].first, Tree[2*node+1].first), 
                max(Tree[2*node].second, Tree[2*node+1].second)};
}

pii qry(int l, int r, int node, int ql, int qr){
    if(qr<l || r<ql) return {INT_MAX, -INT_MAX};
    if(ql<=l && r<=qr) return Tree[node];
    
    int mid=l+r>>1;
    pii x=qry(l, mid, 2*node, ql, qr), y=qry(mid+1, r, 2*node+1, ql, qr);
    
    return {min(x.first, y.first), max(x.second, y.second)};
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        for(int i=0;i<400005;i++) Tree[i]={INT_MAX, -INT_MAX};
        int n, m; scanf("%d%d", &n,&m);
        for(int i=0;i<n;i++){
            arr[i]=i;
            upd(0,n-1, 1, i, i);
        }
        
        while(m--){
            int p,a,b; scanf("%d%d%d",&p,&a,&b);
            if(p==0) {
                swap(arr[a], arr[b]);
                upd(0,n-1, 1, a, arr[a]);
                upd(0,n-1, 1, b, arr[b]);
            } else {
                pii t=qry(0, n-1, 1, a, b);
                if(t.first==a && t.second==b)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
    }
}

 

bottom up 스타일의 세그먼트 트리를 구성하면 arr이 필요없으니 메모리가 절약되긴 할 것이다.