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