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$：判断从第 $l$ 个到第 $r$ 个字符的连续子串是否为一个 正确的括号序列。

输入格式

输入从标准输入按以下格式给出： $N$ $Q$ $S$ $\text{Query}_1$ $\text{Query}_2$ $\vdots$ $\text{Query}_Q$

输出格式

对于每个格式为 $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 \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$ 的查询。在第一个查询中，$(())$ 是一个 正确的括号序列。 在第二个查询中，$(($ 不是一个 正确的括号序列。 在第三个查询中，$)($ 不是一个 正确的括号序列。
在第一个查询中，$(())$ 是一个 正确的括号序列。 在第二个查询中，$S$ 变为 $)()(($。 在第三个查询中，$)()($ 不是一个 正确的括号序列。

标签: AtCoder|abc223F

来源

AtCoder|abc223F