Recover an RBS
Contest: Educational Codeforces Round 132 (Rated for Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, greedy, implementation, strings

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of testcases.

The only line of each testcase contains an RBS with some brackets replaced with question marks. Each character is either '(', ')' or '?'. At least one RBS can be recovered from the given sequence.

The total length of the sequences over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print "YES" if the way to replace question marks with brackets, so that the resulting sequence is an RBS, is unique. If there is more than one way, then print "NO".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, the only possible original RBS is "(())".

In the second testcase, there are multiple ways to recover an RBS.

In the third and the fourth testcases, the only possible original RBS is "()".

In the fifth testcase, the original RBS can be either "((()()))" or "(())()()".

Example input:
5
(?))
??????
()
??
?(?)()?)

Example output:
YES
NO
YES
YES
NO

Editorial:
There are many different approaches to this problem, but I think the model solution has the most elegant one.
First of all, let's construct an RBS from the given string (it always exists, so it is always possible). By calculating the number of opening brackets, closing brackets and questions in the given string, we can compute the number of question marks that should be replaced with opening brackets (it is easy since exactly half of the characters in each RBS are opening brackets). Then, let's form the RBS greedily: replace the first several question marks with opening brackets, and all remaining ones with closed brackets.
Okay, then what about finding a second RBS? Recall that a bracket sequence is an RBS when for each of its positions, the number of closing brackets before it is not greater than the number of opening brackets before it (and these two values should be equal at the end of the sequence, but it is less important now). Consider the segment between the last question mark replaced with an opening bracket, and the first question mark replaced by the closing bracket. If we try to change the order of characters corresponding to question marks, the balance on this segment will decrease at least by $$$2$$$ (since at least one opening bracket to the left of it will become a closing bracket). Is there a way to affect only this segment, and change the balance on it only by $$$2$$$? Yes — just swap the endpoints of this segment (i. e. the last opening bracket that was a question mark and the first closing bracket that was also a question mark). If it yields an RBS, then the answer is NO. Otherwise, the answer is YES since any other permutation of characters that were replacing question marks will also decrease the balance on this segment by at least $$$2$$$.