#P2488. 括号序列
括号序列
问题描述
让我们把正确的括号序列定义为满足以下条件之一的字符串。
- 它是一个空字符串。
- 对于某个正确的括号序列 而言,它是
(
, ,)
按此顺序的连接。 - 它是 、 的连接,依次为某个正确的括号序列 和 。
我们有一个长度为 的字符串 ,由 (
和 )
组成。
给定 个查询 $\text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q$ ,按顺序处理它们。有两种查询,其格式和内容如下。
1 l r
:交换 的 -th 和 -th 字符。2 l r
:判断从 -th到 -th字符的连续子串是否是正确的括号序列。
输入格式
第一行两个整数 和 。
第二行一个长度为 的字符串
接下来 行,每行三个整数代表查询操作。
输出格式
对于格式为 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
在第一个查询中,(())
是一个正确的括号序列。
在第二个查询中, 变成了 )()()
。
在第三个查询中,)()(
不是正确的括号序列。
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 l r
或2 l r
。 - 至少有一个查询的格式是
2 l r
。