括号检查

题目描述

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

• 它是空字符串。
• 它是某个正确的括号序列 $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$ 个字符的连续子串是否为正确的括号序列。

输入格式

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

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

输出格式

对每个格式为 2 l r 的查询，如果该连续子串是正确的括号序列则输出 Yes，否则输出 No，每个查询输出占一行。

样例

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

Yes
No
No

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

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

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

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

Yes
No

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

第二个查询中，$S$ 变为 )()((。

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

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

Yes
No
No

数据范围

• $1 \leq N,Q \leq 2 \times 10^5$
• $S$ 是长度为 $N$、由 ( 和 ) 构成的字符串。
• $1 \leq l \lt r \leq N$
• $N,Q,l,r$ 均为整数。
• 每个查询的格式为 1 l r 或 2 l r。
• 至少存在一个格式为 2 l r 的查询。