分数: 500 点
问题陈述
让我们定义一个 正确的括号序列 作为满足以下条件之一的字符串。
- 这是一个空字符串。
- 这是一个串联
(, A,),按此顺序,对于某些 正确的括号序列 A. - 这是一个串联 A, B,按此顺序,对于某些 正确的括号序列 A 和 B.
我们有一个字符串 S 长度 N 组成 ( 和 ).
鉴于 Q 查询 \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q,按顺序处理。有两种查询,其格式和内容如下。
1 l r:交换 l-th 和 r第一个字符 S.2 l r: 判断是否来自连续的子串 l-th 通过 r- 第一个字符是 正确的括号序列.
约束
- 1 \leq N,Q \leq 2 \times 10^5
- S 是一个长度为的字符串 N 组成
(和). - 1 \leq l < r \leq N
- N,Q,l,r 均为整数。
- 每个查询的格式为
1 l ror2 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