F - Parenthesis Checking Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

  • 空文字列
  • ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
  • ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

( と ) のみからなる長さ N の文字列 S があります。

Q 個のクエリ \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q が与えられるので、順番に処理してください。クエリには 2 種類があり、入力形式とクエリの内容は以下の通りです。

  • 1 l r : S の l 文字目と r 文字目を入れ替える。
  • 2 l r : S の l 文字目から r 文字目までの連続部分文字列が正しい括弧列であるか判定する。

制約

  • 1 \leq N,Q \leq 2 \times 10^5
  • S は ( と ) のみからなる長さ N の文字列
  • 1 \leq l < r \leq N
  • N,Q,l,r はいずれも整数
  • 各クエリは 1 l r、2 l r のいずれかの形式で与えられる。
  • 2 l r の形式のクエリは 1 つ以上与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N Q
S
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q

出力

2 l r の形式の各クエリに対して、連続部分文字列が正しい括弧列である場合 Yes、そうでない場合 No と出力し、改行せよ。

入力例 1

5 3
(())(
2 1 4
2 1 2
2 4 5

出力例 1

Yes
No
No

1 つ目のクエリにおいて、(()) は正しい括弧列です。

2 つ目のクエリにおいて、(( は正しい括弧列ではありません。

3 つ目のクエリにおいて、)( は正しい括弧列ではありません。

入力例 2

5 3
(())(
2 1 4
1 1 4
2 1 4

出力例 2

Yes
No

1 つ目のクエリにおいて、(()) は正しい括弧列です。

2 つ目のクエリによって、S は )()(( となります。

3 つ目のクエリにおいて、)()( は正しい括弧列ではありません。

入力例 3

8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

出力例 3

Yes
No
No

Score : 500 points

Problem Statement

Let us define a correct parenthesis sequence as a string that satisfies one of the following conditions.

  • It is an empty string.
  • It is a concatenation of (, A, ), in this order, for some correct parenthesis sequence A.
  • It is a concatenation of A, B, in this order, for some correct parenthesis sequences A and B.

We have a string S of length N consisting of ( and ).

Given Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q, process them in order. There are two kinds of queries, with the following formats and content.

  • 1 l r: Swap the l-th and r-th characters of S.
  • 2 l r: Determine whether the contiguous substring from the l-th through the r-th character is a correct parenthesis sequence.

Constraints

  • 1 \leq N,Q \leq 2 \times 10^5
  • S is a string of length N consisting of ( and ).
  • 1 \leq l < r \leq N
  • N,Q,l,r are all integers.
  • Each query is in the format 1 l r or 2 l r.
  • There is at least one query in the format 2 l r.

Input

Input is given from Standard Input in the following format:

N Q
S
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q

Output

For each query in the format 2 l r, print Yes if the contiguous substring is a correct parenthesis sequence, and No otherwise, followed by a newline.

Sample Input 1

5 3
(())(
2 1 4
2 1 2
2 4 5

Sample Output 1

Yes
No
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, (( is not a correct parenthesis sequence.

In the third query, )( is not a correct parenthesis sequence.

Sample Input 2

5 3
(())(
2 1 4
1 1 4
2 1 4

Sample Output 2

Yes
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, S becomes )()((.

In the third query, )()( is not a correct parenthesis sequence.

Sample Input 3

8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

Sample Output 3

Yes
No
No