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

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

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

C로 문제풀던 시절에 세그먼트 트리를 공부하고 풀었던 문제이다.

 

어느 구간의 비디오를 빌려올 때 그 구간에 모든 비디오가 다 있는지 체크하는 문제이다.

 

당연히 브루트 포스로 범위 안을 모두 확인해보면 TLE가 난다.

 

문제를 푸는 핵심은 어느 구간 [x, y]의 비디오를 빌려왔다고 가정하면 그 구간의 비디오 번호의 최댓값과 최솟값이 있을 것인데 겹치는 번호를 가진 비디오는 없으므로 구간안에 모든 비디오가 제대로 들어있다면 구간안의 값들의 최대값이 y이고 최솟값이 x라는 것을 이용하는 것이다.

 

최솟값 세그먼트 트리와 최댓값 세그먼트 트리를 만들어서 풀면 된다.

#include <stdio.h>
long long tree[400000], a[400000], max=-1, min=1000000;
long long mintree[400000];

long long gmax(long long x, long long y)
{
    if(x>=y)
        return x;
    else
        return y;
}

long long gmin(long long x, long long y)
{
    if(x<=y)
        return x;
    else
        return y;
}

long long init(int node, int start, int end)
{
    if(start==end)
    {
        return tree[node] = a[start];
    }
    else
    {
        init(node*2, start, (start+end)/2);
        init(node*2+1, (start+end)/2+1, end);
        tree[node] = gmax(tree[node*2],tree[node*2+1]);
    }
}

long long mininit(int node, int start, int end)
{
    if(start==end)
    {
        return mintree[node] = a[start];
    }
    else
    {
        mininit(node*2, start, (start+end)/2);
        mininit(node*2+1, (start+end)/2+1, end);
        mintree[node] = gmin(mintree[node*2],mintree[node*2+1]);
    }
}

void update(int node, int start, int end, int index, long long df)
{
    if(start>index || end<index)
        return;
    if(start!=end)
    {
        update(node*2,start,(start+end)/2,index,df);
        update(node*2+1,(start+end)/2+1,end,index,df);
        tree[node] = gmax(tree[node*2],tree[node*2+1]);
    }
    else
    {
        tree[node] = df;
    }
}

void minupdate(int node, int start, int end, int index, long long df)
{
    if(start>index || end<index)
        return;
    if(start!=end)
    {
        minupdate(node*2,start,(start+end)/2,index,df);
        minupdate(node*2+1,(start+end)/2+1,end,index,df);
        mintree[node] = gmin(mintree[node*2],mintree[node*2+1]);
    }
    else
    {
        mintree[node] = df;
    }
}

void maxq(int node, int start, int end, int left, int right)
{
    if(start>right || end<left)
        return;
    if(start>=left && end<=right)
    {
        max = gmax(max,tree[node]);
        return;
    }
    maxq(node*2,start,(start+end)/2,left,right);
    maxq(node*2+1,(start+end)/2+1,end,left,right);
}

void minq(int node, int start, int end, int left, int right)
{
    if(start>right || end<left)
        return;
    if(start>=left && end<=right)
    {
        min = gmin(min,mintree[node]);
        return;
    }
    minq(node*2,start,(start+end)/2,left,right);
    minq(node*2+1,(start+end)/2+1,end,left,right);
}

int main(){
    int T, N, K, i, j;
    int q, w, e, tmp;
    
    scanf("%d",&T);
    
    while(T--){
        scanf("%d %d",&N,&K);
        for(i=1;i<N+2;i++)
            a[i]=i-1;
        init(1,1,N+1);
        mininit(1,1,N+1);
        for(i=0;i<K;i++){
            max=-1;
            min=1000000;
            scanf("%d %d %d",&q,&w,&e);
            w++;
            e++;
            if(q==0){
                update(1,1,N+1,w,a[e]);
                update(1,1,N+1,e,a[w]);
                minupdate(1,1,N+1,w,a[e]);
                minupdate(1,1,N+1,e,a[w]);
                tmp=a[w];
                a[w]=a[e];
                a[e]=tmp;
            }
            else{
                maxq(1,1,N+1,w,e);
                minq(1,1,N+1,w,e);
                if(min==w-1 && max==e-1){
                    printf("YES\n");
                }
                else{
                    printf("NO\n");
                }
            }
        }
    }
    
    return 0;
}