AT_abc283_d [ABC283D] Scope

题目描述

在由小写英文字母、(、) 组成的字符串中，若可以通过以下步骤变为空字符串，则称其为好字符串：

• 首先，删除所有小写英文字母。
• 然后，只要存在连续的 ()，就将其删除。

例如，((a)ba) 删除所有小写英文字母后变为 (())，然后删除第 $2$ 和第 $3$ 个字符的连续 () 后变为 ()，最终可以变为空字符串，因此是好字符串。

给定一个好字符串 $S$，第 $i$ 个字符记为 $S_i$。

对于每个小写英文字母 a、b、$\ldots$、z，各有一个写有该字母的小球，并有一个空箱子。

高桥君按照 $i = 1, 2, \ldots, |S|$ 的顺序，依次进行如下操作，除非他晕倒：

• 如果 $S_i$ 是小写英文字母，则将写有该字母的小球放入箱子中。如果该小球已经在箱子中，高桥君会晕倒。
• 如果 $S_i$ 是 (，则什么也不做。
• 如果 $S_i$ 是 )，则取 $i$ 之前的整数 $j$，使得 $S$ 的第 $j$ 到第 $i$ 个字符组成的字符串为好字符串，且 $j$ 最大（可以证明这样的 $j$ 一定存在）。将第 $j$ 到第 $i$ 步操作中放入箱子的所有小球从箱子中取出。

请判断高桥君能否在不晕倒的情况下完成所有操作。

输入格式

输入为以下格式，从标准输入读入。

$S$

输出格式

如果高桥君能在不晕倒的情况下完成所有操作，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

((a)ba)

输出 #1

Yes

输入输出样例 #2

输入 #2

(a(ba))

输出 #2

No

输入输出样例 #3

输入 #3

(((())))

输出 #3

Yes

输入输出样例 #4

输入 #4

abca

输出 #4

No

说明/提示

限制

• $1 \leq |S| \leq 3 \times 10^5$
• $S$ 是好字符串

样例解释 1

当 $i = 1$ 时，高桥君什么也不做。$i = 2$ 时，高桥君什么也不做。$i = 3$ 时，高桥君将写有 a 的小球放入箱子。$i = 4$ 时，$4$ 之前最大的 $j$ 使得 $S$ 的第 $j$ 到第 $4$ 个字符组成好字符串是 $2$，因此高桥君将写有 a 的小球从箱子中取出。$i = 5$ 时，高桥君将写有 b 的小球放入箱子。$i = 6$ 时，高桥君将写有 a 的小球放入箱子。$i = 7$ 时，$7$ 之前最大的 $j$ 使得 $S$ 的第 $j$ 到第 $7$ 个字符组成好字符串是 $1$，因此高桥君将写有 a 和 b 的小球从箱子中取出。因此本例答案为 Yes。

样例解释 2

当 $i = 1$ 时，高桥君什么也不做。$i = 2$ 时，高桥君将写有 a 的小球放入箱子。$i = 3$ 时，高桥君什么也不做。$i = 4$ 时，高桥君将写有 b 的小球放入箱子。$i = 5$ 时，写有 a 的小球已经在箱子中，因此高桥君晕倒，后续操作不再进行。因此本例答案为 No。

由 ChatGPT 4.1 翻译