← 返回题目列表

Codeforces · 1340/F

F. 纳斯蒂亚和哥伦比亚广播公司

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

Nastya 是一名有竞争力的程序员,但她现在只是在学习。最近,丹尼斯向她讲述了检查字符串括号序列是否正确的方法。之后,出乎意料的是,纳斯蒂亚提出了一个丹尼斯无法解决的更复杂的问题。你能解决吗?

给出一个字符串 $$$s$$$。它由 $$$k$$$ 种括号对组成。每个括号的形式为 $$$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”。

任何情况下都可以显示所有字母。

示例

输入 #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

注意

在第四个测试中,最初,该字符串不是正确的括号序列,因此第一个查询的答案是“否”。两次更改后,它将等于“$$$1$$$ $$$-1$$$”,因此这是一个正确的括号序列,第四个查询的答案是“是”。