올바른 괄호 문자열과 쿼리

시간 제한2초메모리 제한1024 MB

요약

문자열의 한 글자를 바꾸는 갱신과 구간 질의가 주어질 때, 구간의 '*'를 채워 올바른 괄호 문자열을 만들 수 있는지 판단합니다.

문제

이 문제는 출제자가 어떤 온라인 저지의 문제에서 영감을 얻어, 내용을 거의 그대로 가져와 조금만 수정한 문제입니다.

올바른 괄호 문자열은 다음과 같이 정의된 문자열의 특성입니다.

빈 문자열 $\varnothing$ 은 올바른 괄호 문자열입니다.
$\mathbf{A}$ 가 올바른 괄호 문자열이라면, $\mathbf{A}$ 를 괄호로 둘러싼 $\mathtt{\color{#e74c3c}{(}} \mathbf{A} \mathtt{\color{#e74c3c}{)}}$ 또한 올바른 괄호 문자열입니다.
$\mathbf{A}$ 와 $\mathbf{B}$ 가 올바른 괄호 문자열이라면, 둘을 붙인 $\mathbf{A} \mathbf{B}$ 또한 올바른 괄호 문자열입니다.

길이가 $n$ 이며 '(', ')', '*'로만 이루어진 문자열 $S$ 가 주어집니다. 여러분은 다음 두 종류의 쿼리 $q$ 개를 처리해야 합니다.

1 $i \,\, c$ : $S$ 의 $i$ 번째 문자를 $c$ 로 바꿉니다. $c$ 는 '(', ')', '*' 중 하나입니다. ( $1 \le i \le n$ )
2 $l \,\, r$ : 부분 문자열 $S_lS_{l+1}\cdots S_{r-1}S_r$ 에 있는 '*'를 각각 임의로 '(', ')', 또는 빈 문자열 $\varnothing$ 중 하나로 바꿉니다. 그다음 $\varnothing$ 으로 바꾼 부분을 뺀 나머지를 원래 순서대로 이어 붙였을 때 올바른 괄호 문자열을 만들 수 있는지 구합니다. ( $1 \le l \le r \le n$ )

과연 여러분은 충분히 빠르게 모든 쿼리를 해결할 수 있을까요?

첫 번째 줄에 문자열 $S$ 의 길이 $n$ 과 쿼리의 수 $q$ 가 공백으로 구분되어 주어집니다. ( $1 \le n,q \le 3\cdot 10^5$ )

두 번째 줄에 길이 $n$ 의 문자열 $S$ 가 주어집니다. $S$ 의 모든 문자는 '(', ')', '*' 중 하나입니다.

세 번째 줄부터 $q$ 개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어집니다. 각 쿼리는 위에서 설명한 두 종류 중 하나입니다.

2번 쿼리마다 부분 문자열을 올바른 괄호 문자열로 만들 수 있으면 'Yes', 없으면 'No'를 새 줄에 출력합니다.

예제 1

입력

12 13
(*)())()((*)
2 1 12
2 1 3
2 1 6
2 9 12
2 9 11
1 2 )
2 1 3
2 1 2
2 1 6
1 3 *
2 1 12
1 11 (
2 1 12

예상 출력

Yes
Yes
Yes
Yes
No
No
Yes
No
Yes
No