Scope

题目描述

由小写英文字母、$($ 和 $)$ 组成的字符串如果可以通过以下过程变为空字符串，则称为良好字符串：

首先，移除所有小写英文字母。 然后，反复移除连续的 $()$，直到不可能为止。

例如，$((a)ba)$ 是一个良好字符串，因为移除所有小写英文字母得到 $(())$，可以先在第 $2$ 和第 $3$ 个字符处移除连续的 $()$ 得到 $()$，进而得到空字符串。
给定一个良好字符串 $S$。我们用 $S_i$ 表示 $S$ 的第 $i$ 个字符。 对于每个小写英文字母 $a, b, \ldots, z$，我们有一个写有该字母的球。 此外，我们有一个空箱子。 对于每个 $i = 1,2,\ldots,|S|$，Takahashi 按照顺序执行以下操作，除非他晕倒。

如果 $S_i$ 是小写英文字母，则把写有该字母的球放入箱子。如果该球已经在箱子里，他会晕倒。
如果 $S_i$ 是 $($，不做任何事。
如果 $S_i$ 是 $)$，取小于 $i$ 的最大的整数 $j$，使得第 $j$ 到第 $i$ 个字符组成的是一个良好字符串。（可以证明这样的整数 $j$ 总是存在。）从箱子中取出他在第 $j$ 到第 $i$ 次操作中放入的所有球。

判断 Takahashi 是否可以在不晕倒的情况下完成整个操作序列。

输入格式

输入从标准输入给出，格式如下： $S$

输出格式

如果他可以在不晕倒的情况下完成操作序列，输出 $Yes$；否则输出 $No$。

((a)ba)

Yes

(a(ba))

No

(((())))

Yes

abca

No

提示

$1 \leq |S| \leq 3 \times 10^5$ $S$ 是一个良好字符串。对于 $i = 1$，他不做任何事。
对于 $i = 2$，他不做任何事。
对于 $i = 3$，他把写有 $a$ 的球放入箱子。
对于 $i = 4$，$j=2$ 是小于 $4$ 的最大整数，使得第 $j$ 到第 $4$ 个字符组成的是一个良好字符串，所以他从箱子中取出写有 $a$ 的球。
对于 $i = 5$，他把写有 $b$ 的球放入箱子。
对于 $i = 6$，他把写有 $a$ 的球放入箱子。
对于 $i = 7$，$j=1$ 是小于 $7$ 的最大整数，使得第 $j$ 到第 $7$ 个字符组成的是一个良好字符串，所以他从箱子中取出写有 $a$ 的球和另一个寫有 $b$ 的球。
因此，该测试用例的答案为 $Yes$。
对于 $i = 1$，他不做任何事。
对于 $i = 2$，他把写有 $a$ 的球放入箱子。
对于 $i = 3$，他不做任何事。
对于 $i = 4$，他把写有 $b$ 的球放入箱子。
对于 $i = 5$，寫有 $a$ 的球已經在箱子裡，所以他晕倒，终止操作序列。
因此，该测试用例的答案为 $No$。

标签: AtCoder|abc283D

来源

AtCoder|abc283D