백준17407 괄호 문자열과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/17407

사용 알고리즘

  • Segment Tree

풀이

여는 괄호를 1, 닫는 괄호를 -1로 하고 누적합을 구해봅시다.
올바른 괄호 문자열이 될 조건은, 모든 괄호를 다 더했을 때 0이 나와야하고, 누적합을 구하는 도중에 음수가 나오면 안됩니다.
두 가지 조건을 생각하면서 세그먼트 트리를 짜면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define pb push_back
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> p;

struct Node{
    int sum, mn;
};

Node tree[1 << 18];
int bias = 1 << 17;

void setting(int x, int v){
    x |= bias;
    tree[x].sum = tree[x].mn = v;
    while(x >>= 1){
        tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
        tree[x].mn = min(tree[x << 1].mn, tree[x << 1].sum + tree[x << 1 | 1].mn);
    }
}

void update(int x, int v){
    x |= bias;
    tree[x].sum = tree[x].mn = v / 2;
    while(x >>= 1){
        tree[x].sum += v;
        tree[x].mn = min(tree[x << 1].mn, tree[x << 1].sum + tree[x << 1 | 1].mn);
    }
}

int arr[101010];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    int q; cin >> q;
    s = "#" + s;
    for(int i=1; i<s.size(); i++){
        arr[i] = s[i] == '(' ? 1 : -1;
        setting(i, arr[i]);
    }
    int ans = 0;
    while(q--){
        int t; cin >> t;
        arr[t] *= -1;
        update(t, arr[t] << 1);
        if(tree[1].mn >= 0 && tree[1].sum == 0) ans++;
    }
    cout << ans;
}