백준 20052 - 괄호 문자열?

백준 20052 - 괄호 문자열?

풀이

’(‘를 +1, ‘)’를 -1로 해서 누적합을 계산한 배열 a를 하나 만들자.
이 배열에 대한 min segment tree를 하나 만든다.

l, r이 주어졌을 때,
a[r]-a[l-1] == 0 이고, min(l~r)이 a[r]보다 크거나 같다면 위 쿼리는 성립된다.

a[r]-a[l-1] == 0이라는 건 ‘(‘와 ‘)’의 갯수가 같다는 것이고,
min(l~r)이 a[r]보다 작다는 건 닫을 수 없는 ‘)’가 나왔음을 의미하므로 이보다 크거나 같아야 한다.

코드

#include <bits/stdc++.h>  
  
#define endl "\n"  
#define all(v) (v).begin(), (v).end()  
#define For_IMPL(condition, i, a, b, increment, decrement) \  
    for (int i = (a); condition; (a < b ? increment : decrement))  
#define For(i, a, b) For_IMPL((a < b ? i <= b : i >= b), i, a, b, ++i, --i)  
#define ft first  
#define sd second  
  
using namespace std;  
using ll = long long;  
using lll = __int128_t;  
using ulll = __uint128_t;  
using ull = unsigned long long;  
using ld = long double;  
using pii = pair<int, int>;  
using pll = pair<ll, ll>;  
using ti3 = tuple<int, int, int>;  
using tl3 = tuple<ll, ll, ll>;  
  
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }  
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }  
  
const int INF = 987654321;  
const int INF0 = numeric_limits<int>::max();  
const ll LNF = 987654321987654321;  
const ll LNF0 = numeric_limits<ll>::max();  
  
class Segment {  
public:  
    vector<ll> tree; //tree[node] := a[start ~ end] 의 합  
  
    Segment() {}  
    Segment(int size) {  
        this->resize(size);  
    }  
    void resize(int size) {  
        size = (int) floor(log2(size)) + 2;  
        size = pow(2, size);  
        tree.resize(size, 0);  
    }  
    ll init(vector<ll> &a, int node, int start, int end) {  
        if(start == end) return tree[node] = a[start];  
        else return tree[node] = min(init(a, 2 * node, start, (start + end) / 2),  
                                     init(a, 2 * node + 1, (start + end) / 2 + 1, end));  
    }  
    ll query(int node, int start, int end, int left, int right) {  
        if(right < start || end < left) return INF;  
        if(left <= start && end <= right) return tree[node];  
        return min(query(node * 2, start, (start + end) / 2, left, right),  
                   query(node * 2 + 1, (start + end) / 2 + 1, end, left, right));  
    }  
//    void update(int node, int start, int end, int index, ll value) {  
//        if(index < start || end < index) return;  
//        if(start == end) tree[node] = value;  
//        else {  
//            update(node * 2, start, (start + end) / 2, index, value);  
//            update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);  
//            tree[node] = tree[2*node] + tree[2*node+1];  
//        }  
//    }  
};  
  
void solve() {  
    string s; cin >> s;  
    int n = s.length();  
    vector<ll> a(n+1);  
    a[0] = 0;  
    For(i,1,n) a[i] = a[i-1] + (s[i-1] == '(' ? 1 : -1);  
    Segment tree(n);  
    tree.init(a,1,1,n);  
  
  
    int ans = 0;  
    int q; cin >> q;  
    while(q--) {  
        int l, r; cin >> l >> r;  
        bool res = (a[r]-a[l-1] == 0 and tree.query(1,1,n,l,r) >= a[r]);  
        ans += res;  
    }  
    cout << ans << endl;  
}  
  
int main(void) {  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
  
    int tc = 1;  
//    cin >> tc;  
    while(tc--) {  
        solve();  
//        cout << solve() << endl;  
    }  
  
  
    return 0;  
}