17407번 - 괄호 문자열과 쿼리

괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다.
3. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다.
4. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 괄호 문자열 S = s₁s₂...s_N과 M개의 쿼리가 주어진다. 쿼리는 정수 하나 index로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다.

• S의 i번째 문자가 '('면 ')'로, ')'면 '('로 변경한다.

쿼리의 수행은 누적되며, i번째 쿼리는 i-1번째 쿼리가 수행된 결과에 수행되어야 한다. 각 쿼리를 수행한 결과가 올바른 괄호 문자열이었던 횟수를 모두 세어보자.

첫째 줄에 문자열 S가 주어진다. 둘째 줄에 쿼리의 개수 M이 주어진다. 셋째 줄부터 M개의 줄에 쿼리 index가 한 줄에 하나씩 주어진다.

첫째 줄에 쿼리를 수행한 결과가 올바른 괄호 문자열이었던 횟수를 출력한다.

• 1 ≤ |S| ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ index ≤ |S|

S = "()()()()"에 예제 1의 쿼리를 수행한 결과는 다음과 같다.

• ((()()()
• ((()()))
• ((((()))
• (((())))
• (()())))
• (()())()
• )()())()
• )))())()