102235: [AtCoder]ABC223 F - Parenthesis Checking

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

问题描述

我们定义一个正确的括号序列为满足以下条件之一的字符串。

• 它是空字符串。
• 它是按照以下顺序拼接的(、$A$、)，其中$A$是一个正确的括号序列。
• 它是按照以下顺序拼接的$A$、$B$，其中$A$和$B$都是正确的括号序列。

我们有一个长度为$N$的字符串$S$，由(和)组成。

对于给定的$Q$个查询$\text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q$，按顺序处理它们。有两种类型的查询，格式和内容如下。

• 1 l r：交换$S$中第$l$个和第$r$个字符。
• 2 l r：确定从第$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的。

输入

输入从标准输入中以以下格式给出：

$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

在第一个查询中，(())是一个正确的括号序列。

在第二个查询中，((不是一个正确的括号序列。

在第三个查询中，)(不是一个正确的括号序列。

样例输入2

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

样例输出2

Yes
No

在第一个查询中，(())是一个正确的括号序列。

在第二个查询中，$S$变成了)()((。

在第三个查询中，)()(不是一个正确的括号序列。

样例输入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