F - 括号检查

得分 ： $500$ 分

题目描述

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

• 它是空字符串。
• 它是字符串 (、$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，并换行。

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