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 \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 翻译