#P2488. 括号序列

括号序列

问题描述

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

  • 它是一个空字符串。
  • 对于某个正确的括号序列 AA 而言,它是(AA)按此顺序的连接。
  • 它是 AABB 的连接,依次为某个正确的括号序列 AABB

我们有一个长度为 NN 的字符串 SS ,由 () 组成。

给定 QQ 个查询 $\text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q$ ,按顺序处理它们。有两种查询,其格式和内容如下。

  • 1 l r:交换 SSll -th 和 rr -th 字符。
  • 2 l r:判断从 ll -th到 rr -th字符的连续子串是否是正确的括号序列

输入格式

第一行两个整数 NNQQ

第二行一个长度为 NN 的字符串

接下来 QQ 行,每行三个整数代表查询操作。

输出格式

对于格式为 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

在第一个查询中,(())是一个正确的括号序列

在第二个查询中, SS 变成了 )()()

在第三个查询中,)()(不是正确的括号序列

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

数据范围

  • 1N,Q2×1051 \leq N,Q \leq 2 \times 10^5
  • SS 是长度为 NN 的字符串,由 () 组成。
  • 1l<rN1 \leq l < r \leq N
  • N,Q,l,rN,Q,l,r 都是整数。
  • 每个查询的格式为 1 l r2 l r
  • 至少有一个查询的格式是 2 l r