백준 17407 - 괄호 문자열과 쿼리#

풀이#

(을 +1, )을 -1로 한 다음 누적합을 먼저 계산한다.
이 누적합에 대한 lazy segment tree를 만든다.

만약 x번째 문자를 (에서 )으로 바꾼다면 x ~ n번째(전체 문자길이가 n일 때) 문자까지 누적합을 전부 -2를 시켜주면 되고 그 반대의 경우는 +2를 시켜주면 된다. 위 내용은 구간 업데이트로 lazy update를 사용한다.

문자를 변경했을 때 전체 괄호 누적합의 min이 0보다 크거나 같아야 하고, 전체 누적합의 결과가 0이면 해당 문자열은 올바른 괄호 문자열이다.
즉, 누적합의 lazy seg에서 전체의 min이 0보다 크거나 같고, 마지막 누적합의 값이 0이기만 하면 된다.

코드#

cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define For(i, a, b) for(int i=(a); i<(b); i++)
6#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
7#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
8#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
9#define ft first
10#define sd second
11
12using namespace std;
13using ll = long long;
14using lll = __int128_t;
15using ulll = __uint128_t;
16using ull = unsigned long long;
17using ld = long double;
18using pii = pair<int, int>;
19using pll = pair<ll, ll>;
20using ti3 = tuple<int, int, int>;
21using tl3 = tuple<ll, ll, ll>;
22
23template<typename T> using ve = vector<T>;
24template<typename T> using vve = vector<vector<T>>;
25
26template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
27template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
28
29const int INF = 987654321;
30const int INF0 = numeric_limits<int>::max();
31const ll LNF = 987654321987654321;
32const ll LNF0 = numeric_limits<ll>::max();
33
34struct Lazy {
35    ll val, a, b; // a * val + b
36};
37
38class LazySegment {
39public:
40    vector<Lazy> tree; //tree[node] := a[start ~ end] 의 합
41
42    LazySegment() {}
43    LazySegment(int size) {
44        this->resize(size);
45    }
46    void resize(int size) {
47        size = (int) floor(log2(size)) + 2;
48        size = pow(2, size);
49        tree.resize(size, {0,1, 0});
50    }
51    ll init(vector<ll> &a, int node, int start, int end) {
52        if(start == end) return tree[node].val = a[start];
53        return tree[node].val = min(init(a, 2*node, start, (start+end)/2), init(a, 2*node+1, (start+end)/2+1, end));
54    }
55    void update_lazy(int node, int start, int end) {
56        if(tree[node].a == 1 && tree[node].b == 0) return;
57        tree[node].val = (tree[node].a*tree[node].val + tree[node].b);
58        if(start != end) {
59            for(auto i : {2*node, 2*node+1}) {
60                tree[i].a = (tree[node].a * tree[i].a);
61                tree[i].b = (tree[node].a * tree[i].b + tree[node].b);
62            }
63        }
64        tree[node].a = 1, tree[node].b = 0;
65    }
66    void update(int node, int start, int end, int left, int right, ll a, ll b) {
67        update_lazy(node, start, end);
68        if(right < start || end < left) return;
69        if(left <= start && end <= right) {
70            tree[node].a = (tree[node].a * a);
71            tree[node].b = (tree[node].b + b);
72            update_lazy(node, start, end);
73            return;
74        }
75        update(node * 2, start, (start + end) / 2, left, right, a, b);
76        update(node * 2 + 1, (start + end) / 2 + 1, end, left, right, a, b);
77        tree[node].val = min(tree[2*node].val, tree[2*node+1].val);
78    }
79    ll query(int node, int start, int end, int left, int right) {
80        update_lazy(node, start, end);
81        if(right < start || end < left) return INF;
82        if(left <= start && end <= right) return tree[node].val;
83        return min(query(node * 2, start, (start + end) / 2, left, right),
84                   query(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
85    }
86};
87
88void solve() {
89    string s; cin >> s;
90    int n = s.length();
91    LazySegment seg(n);
92    vector<ll> a(n+1);
93    a[0] = 0;
94    FOR(i,1,n) {
95        a[i] = a[i-1] + (s[i-1] == '(' ? 1 : -1);
96    }
97    seg.init(a,1,1,n);
98
99    int m; cin >> m;
100    int ans = 0;
101    while(m--) {
102        int x; cin >> x;
103        if(s[x-1] == '(') {
104            s[x-1] = ')';
105            seg.update(1,1,n,x,n,1,-2);
106        }
107        else {
108            s[x-1] = '(';
109            seg.update(1,1,n,x,n,1,2);
110        }
111        if(seg.query(1,1,n,1,n) == 0 and seg.query(1,1,n,n,n) == 0) ans++;
112    }
113    cout << ans << endl;
114}
115
116int main(void) {
117    ios_base::sync_with_stdio(false);
118    cin.tie(nullptr);
119    cout.tie(nullptr);
120
121    int TC=1;
122//    cin >> TC;
123    FOR(tc, 1, TC) {
124//        cout << "Case #" << tc << ": ";
125        solve();
126    }
127
128
129    return 0;
130}