백준 20052 - 괄호 문자열 ? [Python]

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

20052번: 괄호 문자열 ?

 

 

L~R까지의 합이 0이면 된다. 누적합과 세그트리를 사용하자

import sys
input = sys.stdin.readline
 
INF = 10 ** 7
 
seg = [0 for _ in range(404040)]
p = [0 for _ in range(101010)]
 
def init(x, s, e):
    if s == e:
        seg[x] = p[s]
        return seg[x]
    mid = (s + e) // 2
    seg[x] = min(init(x * 2, s, mid), init(x * 2 + 1, mid + 1, e))
    return seg[x]
 
def getMin(x, s, e, l, r):
    if e < l or r < s:
        return INF
    if l <= s and e <= r:
        return seg[x]
    mid = (s + e) // 2
    return min(getMin(x * 2, s, mid, l, r), getMin(x * 2 + 1, mid + 1, e, l, r))
 
s = str((input().rstrip()))
for i in range(len(s)):
    p[i + 1] = p[i] + (1 if s[i] == '(' else -1)
 
init(1, 1, len(s))
 
m = int(input())
ans = 0
for queries in range(m):
    i, j = map(int, input().split())
    if getMin(1, 1, len(s), i, j) == p[i - 1] and p[j] == p[i - 1]:
        ans += 1
print(ans)