[백준]괄호 문자열과 쿼리(17407)

문제 링크 : [백준]괄호 문자열과 쿼리(17407)

17407번: 괄호 문자열과 쿼리

 

문제 설명

처음에 괄호로만 이루어진 문자열이 주어집니다.(최대 100,000자)

M번동안 인덱스가 주어지는데, 주어진 인덱스의 괄호를 반대쪽으로 변경합니다.(여는 괄호는 닫는 괄호로, 닫는 괄호는 여는 괄호로)

M번 연산을 수행하면서 옳바른 괄호의 형태를 하는 순간이 몇번이 있었는지를 출력합니다.

입력

S(괄호 문자, 최대 100,000 글자)

M(쿼리의 갯수, 1 <= M <= 100,000)

index

()()()()
8
2
7
4
5
3
7
1
2

 

출력

3

 

카테고리

#세그먼트트리 #LazyPropagation

 

시간 복잡도 상한

O(QlogN)

 

해결 방법

1. 옳바른 괄호 문자는 아래 두가지 조건을 만족해야 합니다.
   1. 여는 괄호와 닫는 괄호의 갯수가 같아야 합니다.
   2. 왼쪽부터 순서대로 여는 괄호와 닫는 괄호의 갯수를 셌을 때, 어느 위치에서도 닫는 괄호의 갯수가 여는 괄호의 갯수보다 커서는 안됩니다.
2. 위 두가지만 만족한다면 항상 옳바른 괄호라고 볼 수 있습니다.
3. 1번 조건은 최초 입력 받았을 때, 각 갯수를 세어놓고, 인덱스가 들어 올 때마다 변경되는 수를 업데이트 해주면 O(Q)번에 연산을 끝낼 수 있습니다.
4. 2번 조건은 왼쪽부터 누적합으로 구하면 되는데, 여는 괄호를 1, 닫는 괄호를 -1로 치환했을 때, 누적합이 음수가 되는 곳이 없어야 합니다.
5. 즉 전체 구간에 걸쳐 각 위치까지의 누적합 중 음수가 되는 구간이 없고, 1번 조건을 만족한다면 옳바른 괄호입니다.
6. 그런데 맨 앞쪽의 괄호가 변경이 된다면, 모든 구간의 누적합이 변경되고, 따라서 모든 구간의 누적합의 최소값도 변경이 됩니다.
7. 따라서 세그먼트 트리로 최소값을 구성하되, 구간에 대한 업데이트가 일어나므로, Lazy Propagation을 사용하여 시간복잡도를 줄일 수 있습니다.

시간복잡도

O(QlogN)

코드

#include<iostream>
#include<algorithm>
#define N 100002
using namespace std;
int n,m,d[N],t[N*4],w,i,l,z[N*4],a,k;
string s;
int in(int p,int l,int r){
    if(l==r)return t[p]=d[l];
    return t[p]=min(in(p*2,l,(l+r)/2),in(p*2+1,(l+r)/2+1,r));
}
void lz(int p,int l,int r){
    if(z[p]){
        t[p]+=z[p];
        if(l!=r)z[p*2]+=z[p],z[p*2+1]+=z[p];
        z[p]=0;
    }
}
int u(int p,int l,int r,int x,int y,int v){
    lz(p,l,r);
    if(y<l||r<x)return t[p];
    if(x<=l&&r<=y)z[p]+=v,lz(p,l,r);
    else t[p]=min(u(p*2,l,(l+r)/2,x,y,v),u(p*2+1,(l+r)/2+1,r,x,y,v));
    return t[p];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>s;
    s="'"+s;
    for(l=1;s[l];l++){
        k=s[l]=='('?1:-1;
        d[l]=d[l-1]+k;
        w+=k;
    }
    l--;
    in(1,1,l);
    cin>>n;
    while(n--){
        cin>>m;
        k=s[m]=='('?-2:2;
        u(1,1,l,m,l,k);
        w+=k;
        s[m]=s[m]=='('?')':'(';
        a+=(t[1]>-1&&!w);
    }
    cout<<a;
}