102833: [Atcoder]ABC283 D - Scope

Problem Statement

A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:

• First, remove all lowercase English letters.
• Then, repeatedly remove consecutive () while possible.

For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the $2$-nd and $3$-rd characters to obtain (), which in turn ends up in an empty string.

You are given a good string $S$. We denote by $S_i$ the $i$-th character of $S$.

For each lowercase English letter a, b, $\ldots$, and z, we have a ball with the letter written on it. Additionally, we have an empty box.

For each $i = 1,2,$ $\ldots$ $,|S|$ in this order, Takahashi performs the following operation unless he faints.

• If $S_i$ is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
• If $S_i$ is (, do nothing.
• If $S_i$ is ), take the maximum integer $j$ less than $i$ such that the $j$-th through $i$-th characters of $S$ form a good string. (We can prove that such an integer $j$ always exists.) Take out from the box all the balls that he has put in the $j$-th through $i$-th operations.

Determine if Takahashi can complete the sequence of operations without fainting.

Constraints

• $1 \leq |S| \leq 3 \times 10^5$
• $S$ is a good string.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print Yes if he can complete the sequence of operations without fainting; print No otherwise.

Sample Input 1

((a)ba)

Sample Output 1

Yes

For $i = 1$, he does nothing.
For $i = 2$, he does nothing.
For $i = 3$, he puts the ball with a written on it into the box.
For $i = 4$, $j=2$ is the maximum integer less than $4$ such that the $j$-th through $4$-th characters of $S$ form a good string, so he takes out the ball with a written on it from the box.
For $i = 5$, he puts the ball with b written on it into the box.
For $i = 6$, he puts the ball with a written on it into the box.
For $i = 7$, $j=1$ is the maximum integer less than $7$ such that the $j$-th through $7$-th characters of $S$ form a good string, so he takes out the ball with a written on it, and another with b, from the box.

Therefore, the answer to this case is Yes.

Sample Input 2

(a(ba))

Sample Output 2

No

For $i = 1$, he does nothing.
For $i = 2$, he puts the ball with a written on it into the box.
For $i = 3$, he does nothing.
For $i = 4$, he puts the ball with b written on it into the box.
For $i = 5$, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.

Therefore, the answer to this case is No.

Sample Input 3

(((())))

Sample Output 3

Yes

Sample Input 4

abca

Sample Output 4

No

问题描述

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

• 首先，删除所有的小写英文字母。
• 然后，反复删除可能的连续的()。

例如，((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$是)，找到一个最大的整数$j$，使得$S$的第$j$个到第$i$个字符形成一个好字符串。（我们可以证明这样的整数$j$总是存在的。）从盒子中取出他在第$j$个到第$i$个操作中放入的所有球。

确定Takahashi是否可以在不昏倒的情况下完成操作序列。

约束

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

输入

输入从标准输入以以下格式给出：

$S$

输出

如果他可以在不昏倒的情况下完成操作序列，打印Yes；否则，打印No。

样例输入1

((a)ba)

样例输出1

Yes

对于$i = 1$，他什么也不做。
对于$i = 2$，他什么也不做。
对于$i = 3$，他将写有a的球放入盒子。
对于$i = 4$，$j=2$是最大的整数，使得$S$的第$j$个到第$4$个字符形成一个好字符串，所以他从盒子中取出写有a的球。
对于$i = 5$，他将写有b的球放入盒子。
对于$i = 6$，他将写有a的球放入盒子。
对于$i = 7$，$j=1$是最大的整数，使得$S$的第$j$个到第$7$个字符形成一个好字符串，所以他从盒子中取出写有a的球，和另一个写有b的球。

因此，这个案例的答案是Yes。

样例输入2

(a(ba))

样例输出2

No

对于$i = 1$，他什么也不做。
对于$i = 2$，他将写有a的球放入盒子。
对于$i = 3$，他什么也不做。
对于$i = 4$，他将写有b的球放入盒子。
对于$i = 5$，写有a的球已经在盒子中，所以他昏倒，操作序列中止。

因此，这个案例的答案是No。

样例输入3

(((())))

样例输出3

Yes

样例输入4

abca

样例输出4

No