CF1838D Bracket Walk

有一个长度为 $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" 都会被认为是肯定的回答。

在第一个样例中： - 第一次询问后，字符串变为 (())()()()。这个字符串本身就是一个合法括号序列，因此只需一直向右走即可。 - 第二次询问后，字符串变为 (())()))()。你可以先向右走一步，再向左走一步，然后一直向右走到字符串末尾，你记录下的字符串为 (((())()))()，这是一个合法括号序列。 - 第三次询问后，字符串变为 ()))()))()。可以证明这个字符串不是可行走的。 在第二个样例中，经过询问后的字符串分别为 ()) 和 ()(，都不是可行走的。 由 ChatGPT 4.1 翻译