목차

괄호 문자열과 쿼리

ps
링크acmicpc.net/…
출처BOJ
문제 번호17407
문제명괄호 문자열과 쿼리
레벨플래티넘 2
분류

구간 쿼리

시간복잡도O(n + mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록44556KB / 2868ms
최고기록2868ms
해결날짜2021/04/02

풀이

코드

"""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()