← 返回题目列表

Codeforces · 1838/D

D. 支架行走

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

有一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“(”和“)”组成。你正走在这根绳子上。首先,您站在 $$$s$$$ 的第一个字符之上,并且您想要进行一系列移动,以便在第 $$$n$$$ 个字符上结束。在一步中,您可以向左移动一个空格(如果您没有站在第一个字符上),也可以向右移动一个空格(如果您没有站在最后一个字符上)。您可能不会停留在同一个地方,但是您可以多次访问任何角色,包括第一个和最后一个角色。

在每个时间点,你写下你当前站立的角色。如果存在一些从第一个字符到最后一个字符的移动序列,使得您写下的字符串是常规的括号序列,我们就说该字符串是可步行的。

常规括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如,括号序列“()()”、“(())”是正则表达式(结果表达式为:“(1)+(1)”、“((1+1)+1)”),而“)(”和“(”则不是。

$$$s=\mathtt{(())()))}$$$ 上的一个可能的有效步行。红点表示您当前的位置,红色字符串表示您写下的字符串。请注意,红色字符串是过程末尾的常规括号序列。

您收到 $$$q$$$ 查询。每个查询都会将字符的值从“(”翻转到“)”,反之亦然。每次查询后,确定字符串是否可步行。

查询是累积的,因此每个查询的影响都会延续到未来的查询。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) - 分别是字符串的大小和查询的数量。

输入的第二行包含一个大小为 $$$n$$$ 的字符串 $$$s$$$,由字符“(”和“)”组成 - 初始括号字符串。

接下来的 $$$q$$$ 行都包含一个整数 $$$i$$$ ($$$1\le i \le n$$$) — 针对该查询要翻转的字符的索引。

输出

对于每个查询,如果该查询之后的字符串可步行,则打印“YES”,否则打印“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

10 9
(())()()))
9
7
2
6
3
6
7
4
8

输出 #1

YES
YES
NO
NO
YES
NO
YES
NO
NO

输入 #2

3 2
(()
2
3

输出 #2

NO
NO

注意

在第一个示例中:

- 第一次查询后,字符串为 (())()()()。该字符串是一个常规的括号序列,因此只需向右移动即可遍历它。
- 第二次查询后,字符串为 (())()))()。如果向右移动一次,然后向左移动一次,然后向右移动直到到达字符串末尾,则会生成字符串 (((())()))(),这是一个常规的括号序列。
- 第三次查询后,字符串为 ()))()))()。我们可以证明这个字符串是不可走的。