BOJ 17407(괄호 문자열과 쿼리)풀이

solved.ac 티어 : 플래 2

www.acmicpc.net/problem/17407

17407번: 괄호 문자열과 쿼리

 

이문제는 딱 봐도 버거운 버거랑 비슷한 문제이다.

버거운 버거를 풀고 오면 거저로 얻는 문제이다.

버거운 버거:joseph0528.tistory.com/8

BOJ 19851(버거운 버거)풀이

버거운 버거에서 변경을 index[i]부터 index[i]으로 바꿔놓고 바로 밑에 전체 구간을 돌려서 추가해야 되는 괄호 개수를 더했을 때 0이면 올바른 괄호 문자열이므로 cnt++를 해주면 끝이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nod{
    ll l1,r1,l2,r2;
};
vector<ll>l(100001);
nod tree[410000];
vector<ll>lazytree(410000);
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,cnt=0;
    scanf("%lld",&a);
    int i;
    char yu[1000005];
    scanf("%s",yu);
    a=strlen(yu);
    for(i=0;i<a;i++){
        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",&q);
        change(1,0,a-1,q-1,q-1);
        nod cn=sumax(1,0,a-1,0,a-1);
        if(cn.l1+cn.r1==0){cnt++;}
    }
    printf("%lld\n",cnt);
}