AT_abc223_f [ABC223F] Parenthesis Checking

题目描述

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

• 空字符串。
• 存在某个正确括号序列 $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：判断 $S$ 的第 $l$ 个字符到第 $r$ 个字符组成的连续子串是否为正确括号序列。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

Yes
No
No

输入输出样例 #2

输入 #2

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

输出 #2

Yes
No

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

说明/提示

限制条件

• $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

第 1 个查询中，(()) 是正确括号序列。
第 2 个查询中，(( 不是正确括号序列。
第 3 个查询中，)( 不是正确括号序列。

样例解释 2

第 1 个查询中，(()) 是正确括号序列。
第 2 个查询后，$S$ 变为 )()((。
第 3 个查询中，)()( 不是正确括号序列。

由 ChatGPT 4.1 翻译