• 올바른 괄호 문자열의 정의는 문제에서 적혀있는대로이지만, 다른 방법으로도 어떤 문자열이 올바른 문자열인지 아닌지를 체크할 수는 있다. 다음 두 조건을 만족하면 된다
  • 전체 문자열에 포함된 '('와 ')'의 갯수가 같다
  • 문자열의 어떤 prefix에 대해서도 '('의 갯수가 ')'의 갯수보다 많거나 같다.
• 이것을 체크하기 쉽게 변수 두개를 도입하자.
  • tot_diff(S) = {S에 포함된 ')'의 수} - {S에 포함된 '('의 수}
  • max_diff(S) = max_i{ {S[:i]에 포함된 ')'의 수} - {S[:i]에 포함된 '('의 수} }
  • 이렇게 두면, tot_diff(S) == 0 이고 max_diff(S) ⇐ 0 이면 S는 올바른 괄호 문자열이다.
• 이제, 각각의 괄호 하나가 리프 노드에 대응되는 세그먼트 트리를 만들자. 각 노드는 tot_diff과 max_diff를 유지한다. S와 T를 자식으로 갖는 부모노드의 값은 max_diff(S+T) = max(tot_diff(S) + max_diff(T), max_diff(S)) 로 구할수 있다.
• 그래서 어떤 부분 문자열이 올바른 괄호인지는, 해당하는 구간에 대해서 쿼리한 값이 조건을 만족하는지를 확인하는 것으로 처리 가능하다.
• 시간 복잡도는 세그먼트 트리를 만드는 데에 O(n)이 걸리고, m개의 업데이트와 m개의 쿼리를 각각 O(logn)에 처리하는 데에 O(mlogn)이 걸리니까, 총 O(n+ mlogn)이다. (n=문자열의 길이)
• 이 문제에서는 항상 전체 문자열에 대한 쿼리만 들어오므로, teflib.segmenttree.SingleRootSegmentTree를 사용해서 이 쿼리를 O(1)에 처리하는 것이 효율적이다. 이렇게 처리하지 않으면, Python으로는 시간 내에 통과하기가 빡빡하다.

"""Solution code for "BOJ 17407. 괄호 문자열과 쿼리".

- Problem link: https://www.acmicpc.net/problem/17407
- Solution link: http://www.teferi.net/ps/problems/boj/17407
"""

import collections
import sys
from teflib import segmenttree

Node = collections.namedtuple('Node', ['max_diff', 'tot_diff'])
LEFT_PAREN = Node(-1, -1)
RIGHT_PAREN = Node(1, 1)


def main():
    S = sys.stdin.readline().rstrip()
    M = int(sys.stdin.readline())
    segtree = segmenttree.SingleRootSegmentTree(
        (LEFT_PAREN if x == '(' else RIGHT_PAREN for x in S),
        merge=lambda l, r: Node(
            max_diff=max(l.tot_diff + r.max_diff, l.max_diff),
            tot_diff=l.tot_diff + r.tot_diff))
    answer = 0
    for _ in range(M):
        index = int(sys.stdin.readline())
        new_node = (LEFT_PAREN if segtree.get(index - 1) is RIGHT_PAREN
                    else RIGHT_PAREN)
        segtree.set(index - 1, new_node)
        tot_diff, max_diff = segtree.query_all_range()
        if tot_diff == 0 and max_diff == 0:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree
• Dependency: teflib.segmenttree.SingleRootSegmentTree