문제

https://www.acmicpc.net/problem/20052


알고리즘

segment tree


풀이

괄호 문자열이 주어지고 쿼리들이 주어졌을 때 부분 문자열이 올바른 괄호 문자열인지를 묻는 문제입니다.

‘(‘을 1로 생각하고 ‘)‘을 -1로 생각했을 때, 올바른 괄호 문자열은 다음과 같은 특징을 갖고 있습니다.

  1. 괄호문자열을 구성하는 문자들의 합은 0이다.

  2. 문자열의 길이를 S라고 할 때, 처음부터 $i (1\leq i \leq S-1)$까지의 문자들의 합은 음수가 되어선 안된다.

1번 조건은 ‘(‘의 등장 횟수와 ‘)‘의 등장 횟수가 일치함을 묻고 있습니다. 2번 조건은 괄호 문자들이 짝을 올바르게 구성하고 있는지를 묻고 있습니다. 만약 주어진 괄호 문자열이 “)(” 라면 총합은 0이 될지언정 올바르게 구성하지는 않습니다.

일반적으로는 스택을 활용하여 선형시간에 해결했지만 이 문제에서는 더 빠르게 처리해야 시간 초과가 발생하지 않습니다.

주어진 괄호문자열을 각각 1과 -1로 치환한 배열을 누적시킨 $psum$ 배열을 만듭니다. 쿼리가 $(L, R)$ 구간에 대해 묻고 있다면 $psum$ 배열을 통해 $L$부터 $i (L\leq i \leq R-1)$ 까지의 부분합을 빠르게 구할 수 있습니다. $psum[i]-psum[L-1]$ 로 부분합을 구하게 되는데 이 값 중에 음수가 있는지 검사하기 위해선 가장 음수를 잘 만드는 후보에 대해서만 검사를 하면 됩니다. 고정된 $psum [L-1]$에 대해서는 고려할 필요 없으므로 $psum [i]$중에서 가장 작은 값을 찾아 그 부분합이 음수를 만드는지 확인하면 됩니다. 이를 위해 최솟값을 저장하는 세그먼트 트리를 만들어 문제를 해결했습니다.

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e5;
#define left i << 1
#define right i << 1 | 1

string s;
int Q, ans, N;
int tree[MAXN << 1];

inline int query(int l, int r) {
    int ret = 1e5;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
        ret = min(ret, tree[l++]);
        ret = min(ret, tree[r--]);
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> s;
    N = s.size();
    for (int i = 0; i < N; ++i) {
        tree[N + i] = tree[N + i - 1] + (s[i] == '(' ? 1 : -1);
    }
    for (int i = N - 1; i > 0; --i) {
        tree[i] = min(tree[left], tree[right]);
    }

    cin >> Q;
    while (Q--) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int minus = (u == 0 ? 0 : tree[N + u - 1]);
        bool con1 = (query(u, v) - minus) >= 0;
        bool con2 = (tree[N + v] - minus) == 0;
        ans += (con1 & con2);
    }
    cout << ans;

    return 0;
}