BOJ 6164(Hotel)풀이

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

6164번: Hotel

이문제는 일자로 나열된 방들이 있고 1번 쿼리는 소들은 n개가 연속되게 비어있는 방을 쓸려고 하는데 이때 그런 방이 있다면 연속된 n개방에서 가장 왼쪽 방의 번호 중 가장 작은 값을 출력하고 그 부분을 사용 중으로 바꾸고 그런 방이 없다면 0을 출력하는 것이고 2번 쿼리는 n부터 n+D_i-1까지 비어있음으로 바꾸는 쿼리로 구성된 문제다

일단 이 문제는 레이지프로퍼게이션으로 풀 수 있는데

해당 위치가 비어있으면 0 아니면 1이라고 하자

2번 쿼리는 레이지로 생각했을때 n~n+D_i-1 부분을 0으로 바꾸는 쿼리가 된다.

1번 쿼리가 어려운데 트리를 만들었을 때 tree [n]은 현재 위치의 구간에서 가장 왼쪽부터 연속된 0의 개수와 왼쪽의 위치, 반대로 가장 오른쪽에서부터 연속된 0의 개수와 오른쪽에서 연속된 0의 위치 중 가장 작은 값 즉 왼쪽 위치, 마지막으로 현재 구간까지 가장 큰 연속 구간의 값 이렇게 5개를 담는다.

이렇게 만든 이유는 왼쪽,오른쪽에서 연속된 0의 개수를 제외한 중간에 있는 애들은 양쪽에 있는 애들이랑 이어져야지만 다른 tree [n]이랑 이어질 수 있다. 또 왼쪽과 오른쪽은 거리가 먼 tree [n]과 이어질 수 있는지 판별해야 되기 때문에 필요하다.

이제 구현해보자

struct nd{
    ll lidx,lcnt,ridx,rcnt,mv;
};

일단 5개를 만들고

nd seg(ll n,ll s,ll e){
    tree1[n]=-1;
    if(s==e){return tree[n]={s,1,e,1,1};}
    nd left=seg(n*2,s,(s+e)/2),right=seg(n*2+1,(s+e)/2+1,e);
    return tree[n]=pr(left,right,s,e);    
}

레이지 세그의 틀을 만들어 준다.

일반 레이지 세그와 달리 저기선 pr(left, right, s, e); 이렇게 했는데 pr이 모든 tree [n]를 위의 내용과 같이 만들어 주는 함수이다.(두 tree [n*2],tree[n*2+1]를 tree[n]으로 합치는 함수)

nd pr(nd a,nd b,ll s,ll e){
    ll cn=0,lt=0,lx=a.lidx,rt=0,rx=0,m=(s+e)/2,mf=max(a.mv,b.mv);
    if(a.rcnt!=0&b.lcnt!=0){
        mf=max(mf,a.rcnt+b.lcnt);
        cn=1;
    }
    if(a.lcnt!=0&&cn!=0&&a.lcnt==m-s+1){
        mf=max(mf,m-s+1+b.lcnt);
        lt=(m-s+1)+b.lcnt;
    }else{lt=a.lcnt;}
    if(b.rcnt!=0&&cn!=0&&b.rcnt==e-(m+1)+1){
        mf=max(mf,e-(m+1)+1+a.rcnt);
        rt=e-(m+1)+1+a.rcnt;
        rx=a.ridx;
    }else{
        rt=b.rcnt;
        rx=b.ridx;
    }
    mf=max({mf,lt,rt});
    return{lx,lt,rx,rt,mf};
}

여기서 a는 tree[n*2], b는 tree [n*2+1]이다.

일단 지금까지 가장 큰 연속 구간의 개수를 mf으로 잡고 a구간에서 최댓값 mv와 b구간에서 최대값 mv, 그리고 두 구간을 합치면서 생기는 구간의 개수를 모두 max 했을 때의 값을 mf에 넣어준다.

이제 나머지를 합쳐주면 되는데 이때 a의 오른쪽에서 연속된 구간과 b의 왼쪽에서 연속된 구간이 합쳐질 수 있는지 확인해야 되는데 그것은 양쪽 구간의 개수가 0이 아니라면 합쳐지는 것이기 때문에 합쳐주고 왼쪽 값을 저장한다.

이제 중앙을 판별했으니 그 중앙과 왼쪽, 오른쪽이 합쳐지는 여부에 따라 왼쪽 위치와 개수, 오른쪽에서 가장 왼쪽 위치와 개수를 구해주면 된다.

이러면 이제 두 구간을 합쳐주는 함수는 완성이다.

이제 change(구간 변경 함수)와 propagate를 설명하겠다

이것들은 기초 세그 레이지의 코드와 별 차이가 없다.

void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){
        tree1[n]=f;
        propagate(n,s,e);
        return;
    }
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=pr(tree[n*2],tree[n*2+1],s,e);
}

이 문제에선 구간을 0으로 바꾸는 2번 쿼리와 출력을 하고 출력한 위치부터 입력값만큼의 구간을 1로 바꾸는 1번 쿼리 이렇게 두 개의 변경이 필요 하니 이렇게 구현해주면 된다. 마지막에 tree [n*2], tree [n*2+1]를 합치는 코드는 위와 같이 pr에 넣어주면 된다.

void propagate(ll n,ll s,ll e){
    if(tree1[n]!=-1){
        if(s!=e){
            tree1[n*2]=tree1[n];
            tree1[n*2+1]=tree1[n];
        }
        if(tree1[n]==1)tree[n]={0,0,0,0,0};
        if(tree1[n]==0)tree[n]={s,(e-s)+1,s,(e-s)+1,(e-s)+1};
        tree1[n]=-1;
    }
}

이 propagate도 별 차이는 없는데 tree1 [n]이 1일경우 구간에 사람이 들어가 있다는 뜻이니 빈공간이 없다로 해주면된다 즉 모든 값을 0으로 바꿔주면 된다.

tree1[n]이 0일 경우 그 구간은 비어있다는 뜻이니 구간의 왼쪽 값과 크기를 두 번씩 넣어주고 마지막에도 구간 크기를 넣어주면 된다.

 

ll ans(ll n,ll s,ll e,ll v){
    if(tree[n].mv<v)return inf;
    propagate(n,s,e);
    if(tree[n].lcnt==e-s+1)return tree[n].lidx;
    ll m=(s+e)/2;
    ll ck=10;
    ll mi=inf;
    if(s!=e){
        propagate(n*2,s,m);
        propagate(n*2+1,m+1,e);
        if(tree[n*2].lcnt>=v)return tree[n*2].lidx;
        else{
            if((m-s+1)-(tree[n*2].lcnt+tree[n*2].rcnt)>=v&&tree1[n*2]!=1)mi=min(mi,ans(n*2,s,m,v));
            if(tree[n*2].rcnt>=v)mi=min(mi,tree[n*2].ridx);
            if(tree[n*2].rcnt+tree[n*2+1].lcnt>=v){
                if(tree[n*2].rcnt!=0)mi=min(mi,tree[n*2].ridx);
                else mi=min(mi,tree[n*2+1].lidx);
            }
            if(mi!=inf)return mi;
        }
        if(tree[n*2+1].lcnt>=v)return tree[n*2+1].lidx;
        if((e-(m+1)+1)-(tree[n*2+1].lcnt+tree[n*2+1].rcnt)>=v&&tree1[n*2+1]!=1)mi=min(mi,ans(n*2+1,m+1,e,v));
        if(tree[n*2+1].rcnt>=v)mi=min(mi,tree[n*2+1].ridx);
    }
    return mi;
}

이제 가장 중요한 출력 함수다.

위에서부터 설명하면 일단 현재 구간에서 가장 큰 연속 구간이 v(입력으로 들어온 값) 보다 작다면 그 구간에선 가능한 위치가 나올 수 없기 때문에 inf을 리턴한다(inf는 절대로 나올 수 없는 큰 위치를 넣어주면 된다. n이 50000이니 50001 넣어도 된다.) 그다음으로 현재 구간의 개수랑 연속 구간의 개수가 같다면 위에서 현재 구간에서 연속된 구간이 v보다 크니 무조건 이 구간에서 가장 왼쪽 값이 가장 작은 위치가 되기 때문에 가장 왼쪽 값을 return 해준다.

이제 왼쪽부터 순서대로 탐색을 해주는 것인데 왼쪽 연속 구간이 v보다 크다면 그 연속 구간의 왼쪽 값을 리턴하고 아닐 경우 왼쪽과 오른쪽 구간 사이의 구간이 개수가 v보다 클 경우 그 구간을 탐색하기 위에 ans(n*2, s, m, v)를 해주고 그다음에 tree [n*2]에서 오른쪽 구간이 v보다 크다면 앞에서 탐색한 중간구간의 위치와 또 tree [n*2]의 오른쪽 구간과 tree[n*2+1]의 왼쪽 구간을 합쳤을때 v가 넘는다면 tree[n*2]의 오른쪽 구간의 왼쪽 값까지 비교해서 가장 작은 값이 inf가 아니라면 리턴한다.

이제 마지막으로 tree [n*2+1]에서의 왼쪽 구간, 가운데 구간, 오른쪽 구간을 탐색해서 작은 값을 리턴해주면 된다.

이제 이렇게 해주면 inf 또는 위치 값이 나오는데 inf일 경우 0을 출력하고 아닌 경우 리턴된 위치부터 v개의 위치에 구간을 1로 바꾸는 쿼리를 사용하면 끝이다.