Nastya and CBS

题意翻译

你需要动态维护一个多种括号组成的括号序列。需要支持两种操作： - $1$ $i$ $t$：修改 $i$ 位置的括号为 $t$（绝对值表示种类，正数表示是左括号，负数表示是右括号）。 - $2$ $l$ $r$：查询 $[l, r]$ 区间是否是一个合法的括号序列。 序列长度为 $n$，不同的括号种类数为 $k$，操作次数为 $q$。 一个多种括号组成的括号序列 $S$ 是合法的当且仅当： 1. $S$ 为空。 2. $S$ 可以表示为 $A + B$ 的形式，其中 $A, B$ 都是合法的。 3. $S$ 可以表示为 $\texttt{(}^\ast + A + \texttt{)}^\ast$ 的形式，其中 $A$ 是合法的并且 $\texttt{(}^\ast$ 与 $\texttt{)}^\ast$ 是一对**相同种类的左右括号**。 例如 `()[{}()]` 和 `{([{}])}` 是合法的，而 `][][` 和 `([{)]}` 不是。

题目描述

Nastya is a competitive programmer, but she is only studying now. Recently, Denis told her about the way to check if the string is correct bracket sequence. After that, unexpectedly, Nastya came up with a much more complex problem that Denis couldn't solve. Can you solve it? A string $ s $ is given. It consists of $ k $ kinds of pairs of brackets. Each bracket has the form $ t $ — it is an integer, such that $ 1 \leq |t| \leq k $ . If the bracket has a form $ t $ , then: - If $ t > 0 $ , then it's an opening bracket of the type $ t $ . - If $ t < 0 $ , then it's a closing bracket of the type $ -t $ . Thus, there are $ k $ types of pairs of brackets in total. The queries need to be answered: 1. Replace the bracket at position $ i $ with the bracket of the form $ t $ . 2. Check if the substring from the $ l $ -th to $ r $ -th position (including) is the correct bracket sequence. Recall the definition of the correct bracket sequence: - An empty sequence is correct. - If $ A $ and $ B $ are two correct bracket sequences, then their concatenation " $ A $ $ B $ " is also correct bracket sequence. - If $ A $ is the correct bracket sequence, $ c $ $ (1 \leq c \leq k) $ is a type of brackets, then the sequence " $ c $ $ A $ $ -c $ " is also correct bracket sequence.

输入输出格式

输入格式

The first line contains an integer $ n $ $ (1 \leq n \leq 10^5) $ — length of string and $ k $ $ (1 \leq k \leq n) $ — the number of kinds of pairs of brackets. The second line contains string $ s $ of length $ n $ — $ n $ integers $ s_1, s_2, \ldots, s_n $ $ (1 \leq |s_i| \leq k) $ The third line contains single integer $ q $ $ (1 \leq q \leq 10^5) $ — the number of queries. Each of the following $ q $ lines describes the queries: - $ 1 $ $ i $ $ t $ - query of the $ 1 $ type $ (1 \leq i \leq n, 1 \leq |t| \leq k) $ . - $ 2 $ $ l $ $ r $ - query of the $ 2 $ type $ (1 \leq l \leq r \leq n) $ .

输出格式

For each query of $ 2 $ type, output "Yes" if the substring from the query is the correct bracket sequence and "No", otherwise. All letters can be displayed in any case.

输入输出样例

输入样例 #1

2 1
1 -1
1
2 1 2

输出样例 #1

Yes

输入样例 #2

2 2
1 -2
1
2 1 2

输出样例 #2

No

输入样例 #3

6 2
1 2 -2 -1 1 -1
3
2 1 6
2 1 4
2 2 5

输出样例 #3

Yes
Yes
No

输入样例 #4

2 2
-1 1
4
2 1 2
1 1 1
1 2 -1
2 1 2

输出样例 #4

No
Yes

说明

In the fourth test, initially, the string is not a correct bracket sequence, so the answer to the first query is "No". After two changes it will be equal to " $ 1 $ $ -1 $ ", so it is a correct bracket sequence and the answer to the fourth query is "Yes".

题意翻译

你需要动态维护一个多种括号组成的括号序列。需要支持两种操作： - $1$ $i$ $t$：修改 $i$ 位置的括号为 $t$（绝对值表示种类，正数表示是左括号，负数表示是右括号）。 - $2$ $l$ $r$：查询 $[l, r]$ 区间是否是一个合法的括号序列。 序列长度为 $n$，不同的括号种类数为 $k$，操作次数为 $q$。 一个多种括号组成的括号序列 $S$ 是合法的当且仅当： 1. $S$ 为空。 2. $S$ 可以表示为 $A + B$ 的形式，其中 $A, B$ 都是合法的。 3. $S$ 可以表示为 $\texttt{(}^\ast + A + \texttt{)}^\ast$ 的形式，其中 $A$ 是合法的并且 $\texttt{(}^\ast$ 与 $\texttt{)}^\ast$ 是一对**相同种类的左右括号**。 例如 `()[{}()]` 和 `{([{}])}` 是合法的，而 `][][` 和 `([{)]}` 不是。