← 返回题目列表

AtCoder · abc223_f

I. 括号检查

中文机器翻译题面 查看原题

分数: 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 r or 2 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