CF1340F Nastya and CBS

Nastya 是一名竞赛程序员，但她目前还在学习。最近，Denis 告诉了她一种判断字符串是否为合法括号序列的方法。在此之后，Nastya 意外地想出了一个更复杂的问题，Denis 没能解决。你能解决吗？ 给定一个字符串 $s$，它由 $k$ 种括号对组成。每个括号的形式为 $t$，其中 $t$ 是一个整数，满足 $1 \leq |t| \leq k$。如果括号的形式为 $t$，则： - 如果 $t > 0$，则它是类型为 $t$ 的左括号。 - 如果 $t < 0$，则它是类型为 $-t$ 的右括号。 因此，总共有 $k$ 种括号对。 你需要回答以下两种操作： 1. 将第 $i$ 个位置的括号替换为形式为 $t$ 的括号。 2. 判断从第 $l$ 个到第 $r$ 个位置（包含两端）组成的子串是否为合法括号序列。 合法括号序列的定义如下： - 空序列是合法的。 - 如果 $A$ 和 $B$ 都是合法括号序列，则它们的连接 "$A$ $B$" 也是合法括号序列。 - 如果 $A$ 是合法括号序列，$c$（$1 \leq c \leq k$）是一种括号类型，则序列 "$c$ $A$ $-c$" 也是合法括号序列。

第一行包含两个整数 $n$（$1 \leq n \leq 10^5$）——字符串的长度，以及 $k$（$1 \leq k \leq n$）——括号对的种类数。 第二行包含长度为 $n$ 的字符串 $s$，即 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \leq |s_i| \leq k$）。 第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）——操作的数量。 接下来的 $q$ 行，每行描述一个操作： - $1\ i\ t$——类型 $1$ 的操作（$1 \leq i \leq n, 1 \leq |t| \leq k$）。 - $2\ l\ r$——类型 $2$ 的操作（$1 \leq l \leq r \leq n$）。

对于每个类型 $2$ 的操作，如果查询的子串是合法括号序列，输出 "Yes"，否则输出 "No"。 输出时字母大小写不限。

在第四个测试点中，初始字符串不是合法括号序列，所以第一个查询的答案是 "No"。经过两次修改后，字符串变为 "$1\ -1$"，此时是合法括号序列，因此第四个查询的答案是 "Yes"。 由 ChatGPT 4.1 翻译