BOJ 19851(버거운 버거)풀이

세그 레이지를 이용했습니다.

 

solved.ac 티어 : 다이아 5

www.acmicpc.net/problem/19851

19851번: 버거운 버거

이문제는 금광세그로 하는 풀이도 있지만 세그 레이지로 풀이하겠다..

 

풀이는 구간에서 남는 )의 개수와 (의 개수를 구하는 방식이다.

배열에 원래 구간과 반전했을때의 구간을 저장하고 변경이 일어날 때마다 2개의 구간을 반전시키면서 바꿔준다.

 

처음에 트리를 만들때 struct으로 트리안에 배열을 넣어서 트리를 만든다.

 

void seg(ll n,ll s,ll e){
    if(s==e){  // 왼쪽 괄호일경우 남는 왼쪽괄호에 1 오른쪽에 0과 반전한  0,1로 해놓고 오른쪽괄호일경우 0 1 1 0으로 하면된다.
        if(l[s]==1){tree[n]={1,0,0,1};return;}
        else{tree[n]={0,1,1,0};return;}
    }
    seg(n*2,s,(s+e)/2);
    seg(n*2+1,(s+e)/2+1,e);
    
    tree[n]={0,0,0,0};
    //두개의 구간에서 왼쪽 구간에서의 남는 (의 개수와 오른쪽 구간에서의 남는 )의 개수를 비교해서 (의 개수가 더 크면 두 수의 차만큼 지금위치 배열의 (위치에 넣고 )의 개수가 더 크면 두수의 차만큼 지금위치 배열의 )위치에 값을 넣는다. 
    if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
    else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
    // 오른쪽 구간에서의 왼쪽값을 지금위치 배열의 왼쪽에 넣어주고 왼쪽 구간에서의 오른쪽값을 지금위치 배열의 오른쪽에 넣어준다.
    tree[n].l1+=tree[n*2+1].l1;
    tree[n].r1+=tree[n*2].r1;
    // 위랑 같은 방식은 반전 구간에도 적용해준다.
    if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
    else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
    tree[n].l2+=tree[n*2+1].l2;
    tree[n].r2+=tree[n*2].r2;
}

s==e구간에서 배열의 값이 1이면(")"일 경우) 왼쪽 괄호에 1 오른쪽에 0과 반전한  0,1로 해놓고 아니면 오른쪽 괄호일 경우 0 1 1 0으로 해준다.

 

구간을 합치는거는 위에 주석에 쓰여있는 거처럼 두 개의 구간에서 왼쪽 구간에서의 남는 (의 개수와 오른쪽 구간에서의 남는 )의 개수를 비교해서 (의 개수가 더 크면 두 수의 차만큼 지금 위치 배열의 (위치에 넣고 )의 개수가 더 크면 두 수의 차만큼 지금 위치 배열의 ) 위치에 값을 넣고 오른쪽 구간에서의 왼쪽 값을 지금 위치 배열의 왼쪽에 넣어주고 왼쪽 구간에서의 오른쪽 값을 지금 위치 배열의 오른쪽에 넣어준다.

그리고 반전 배열도 만들어서 업데이트 할때 반전해줘야 되기 때문에 반전 배열도 똑같이 해준다.

 

nod sumax(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return{0,0,0,0};}
    if(left<=s&&e<=right){return tree[n];}
    
    nod le=sumax(n*2,s,(s+e)/2,left,right);
    nod ri=sumax(n*2+1,(s+e)/2+1,e,left,right);
    nod c;
    c={0,0,0,0};
    // 여기도 세그트리를 만들때 처럼 해준다.
    if(le.l1>ri.r1){c.l1=le.l1-ri.r1;}
    else{c.r1=ri.r1-le.l1;}
    c.l1+=ri.l1;
    c.r1+=le.r1;
    if(le.l2>ri.r2){c.l2=le.l2-ri.r2;}
    else{c.r2=ri.r2-le.l2;}
    c.l2+=ri.l2;
    c.r2+=le.r2;
    return c;
}

이제 트리를 만들때와 같이 구간을 합쳤을 때의 남는 개수를 return 하면 된다.

 

void propagate(ll n,ll s,ll e){
    if(lazytree[n]!=0){
        if(s!=e){
            lazytree[n*2]+=1;
            lazytree[n*2+1]+=1;
            lazytree[n*2]%=2;
            lazytree[n*2+1]%=2;
            //트리를 1또는 0으로 바꿔준다.
        }
        ll io=tree[n].l1,ii=tree[n].r1;
        tree[n].l1=tree[n].l2;
        tree[n].r1=tree[n].r2;
        tree[n].l2=io;
        tree[n].r2=ii;
        lazytree[n]=0;
    }
}

프로퍼 게이트는 1 또는 0으로 바꿔서 1일 경우 반전한다. 처음엔 +1만 해줘서 똑같은 구간을 2번 했을 때 반전 안되게 해야 되지만 반전이 돼서 틀려서 0으로 바꿔서 반전 안되게 바꿔줬습니다.

 

변경도 다른곳과 똑같이 return 하는 부분을 세그 트리에서 했던 거처럼 해주면 된다.

 

void change(ll n,ll s,ll e,ll s1,ll e1){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){
        lazytree[n]=1;
        propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1);
    change(n*2+1,(s+e)/2+1,e,s1,e1);
    tree[n]={0,0,0,0};
    // 여기도 세그트리를 만들때 처럼 해준다. 
    if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
    else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
    tree[n].l1+=tree[n*2+1].l1;
    tree[n].r1+=tree[n*2].r1;
    
    if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
    else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
    tree[n].l2+=tree[n*2+1].l2;
    tree[n].r2+=tree[n*2].r2;
}

 

이제 코드를 완성해서 제출하면 맞는다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nod{
    ll l1,r1,l2,r2;
};
vector<ll>l(1000001);
nod tree[2100000];
vector<ll>lazytree(2100000);
ll a;
void seg(ll n,ll s,ll e){
    if(s==e){  // 왼쪽 괄호일경우 남는 왼쪽괄호에 1 오른쪽에 0과 반전한  0,1로 해놓고 오른쪽괄호일경우 0 1 1 0으로 하면된다.
        if(l[s]==1){tree[n]={1,0,0,1};return;}
        else{tree[n]={0,1,1,0};return;}
    }
    seg(n*2,s,(s+e)/2);
    seg(n*2+1,(s+e)/2+1,e);
    
    tree[n]={0,0,0,0};
    //두개의 구간에서 왼쪽 구간에서의 남는 (의 개수와 오른쪽 구간에서의 남는 )의 개수를 비교해서 (의 개수가 더 크면 두 수의 차만큼 지금위치 배열의 (위치에 넣고 )의 개수가 더 크면 두수의 차만큼 지금위치 배열의 )위치에 값을 넣는다. 
    if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
    else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
    // 오른쪽 구간에서의 왼쪽값을 지금위치 배열의 왼쪽에 넣어주고 왼쪽 구간에서의 오른쪽값을 지금위치 배열의 오른쪽에 넣어준다.
    tree[n].l1+=tree[n*2+1].l1;
    tree[n].r1+=tree[n*2].r1;
    // 위랑 같은 방식은 반전 구간에도 적용해준다.
    if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
    else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
    tree[n].l2+=tree[n*2+1].l2;
    tree[n].r2+=tree[n*2].r2;
}
void propagate(ll n,ll s,ll e){
    if(lazytree[n]!=0){
        if(s!=e){
            lazytree[n*2]+=1;
            lazytree[n*2+1]+=1;
            lazytree[n*2]%=2;
            lazytree[n*2+1]%=2;
            //트리를 1또는 0으로 바꿔준다.
        }
        ll io=tree[n].l1,ii=tree[n].r1;
        tree[n].l1=tree[n].l2;
        tree[n].r1=tree[n].r2;
        tree[n].l2=io;
        tree[n].r2=ii;
        lazytree[n]=0;
    }
}
nod sumax(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return{0,0,0,0};}
    if(left<=s&&e<=right){return tree[n];}
    
    nod le=sumax(n*2,s,(s+e)/2,left,right);
    nod ri=sumax(n*2+1,(s+e)/2+1,e,left,right);
    nod c;
    c={0,0,0,0};
    // 여기도 세그트리를 만들때 처럼 해준다.
    if(le.l1>ri.r1){c.l1=le.l1-ri.r1;}
    else{c.r1=ri.r1-le.l1;}
    c.l1+=ri.l1;
    c.r1+=le.r1;
    if(le.l2>ri.r2){c.l2=le.l2-ri.r2;}
    else{c.r2=ri.r2-le.l2;}
    c.l2+=ri.l2;
    c.r2+=le.r2;
    return c;
}
void change(ll n,ll s,ll e,ll s1,ll e1){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){
        lazytree[n]=1;
        propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1);
    change(n*2+1,(s+e)/2+1,e,s1,e1);
    tree[n]={0,0,0,0};
    // 여기도 세그트리를 만들때 처럼 해준다. 
    if(tree[n*2].l1>tree[n*2+1].r1){tree[n].l1=tree[n*2].l1-tree[n*2+1].r1;}
    else{tree[n].r1=tree[n*2+1].r1-tree[n*2].l1;}
    tree[n].l1+=tree[n*2+1].l1;
    tree[n].r1+=tree[n*2].r1;
    
    if(tree[n*2].l2>tree[n*2+1].r2){tree[n].l2=tree[n*2].l2-tree[n*2+1].r2;}
    else{tree[n].r2=tree[n*2+1].r2-tree[n*2].l2;}
    tree[n].l2+=tree[n*2+1].l2;
    tree[n].r2+=tree[n*2].r2;
}
int main()
{
    ll b,c,d,q,k,gh,gk;
    scanf("%lld",&a);
    int i;
    char yu[1000005];
    scanf("%s",yu);
    for(i=0;i<a;i++){  // 왼쪽괄호는 1 오른쪽 괄호는 -1로해서 판별
        if(yu[i]=='('){l[i]=1;}
        else{l[i]=-1;}
    }
    seg(1,0,a-1);
    scanf("%lld",&b);
    for(i=0;i<b;i++){
        scanf("%lld %lld %lld",&q,&c,&d);
        if(q==2){
            nod cn=sumax(1,0,a-1,c-1,d-1);
            printf("%lld\n",(d-c+1)+cn.l1+cn.r1);//구간의 개수와 왼쪽,오른쪽 남는 개수를 모두 더해주고 출력한다.
        }else{change(1,0,a-1,c-1,d-1);}
    }
}

(전체코드) 복붙은 하지 맙시다

 

비슷한 거나 추천 문제

www.acmicpc.net/problem/20052

20052번: 괄호 문자열 ?

변경만 없는 같은 문제이다.

 

www.acmicpc.net/problem/17407

17407번: 괄호 문자열과 쿼리

한 구간만 변경하는 같은 문제이다.