AmShZ Wins a Bet
Contest: Codeforces Global Round 17
Difficulty rating: 3300
Tags: data structures, greedy, hashing

Right before the UEFA Euro 2020, AmShZ and Safar placed bets on who'd be the champion, AmShZ betting on Italy, and Safar betting on France.

Of course, AmShZ won. Hence, Safar gave him a bracket sequence $$$S$$$. Note that a bracket sequence is a string made of '(' and ')' characters.

AmShZ can perform the following operation any number of times:

- First, he cuts his string $$$S$$$ into three (possibly empty) contiguous substrings $$$A, B$$$ and $$$C$$$. Then, he glues them back by using a '(' and a ')' characters, resulting in a new string $$$S$$$ = $$$A$$$ + "(" + $$$B$$$ + ")" + $$$C$$$.For example, if $$$S$$$ = "))((" and AmShZ cuts it into $$$A$$$ = "", $$$B$$$ = "))", and $$$C$$$ = "((", He will obtain $$$S$$$ = "()))((" as a new string.

After performing some (possibly none) operations, AmShZ gives his string to Keshi and asks him to find the initial string. Of course, Keshi might be able to come up with more than one possible initial string. Keshi is interested in finding the lexicographically smallest possible initial string.

Your task is to help Keshi in achieving his goal.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The only line of input contains a single string $$$S$$$ — the string after the operations $$$(1\le |S|\le 3 \cdot 10^5)$$$.

It is guaranteed that the first character of $$$S$$$ is ')'.

Output format:
Print the lexicographically smallest possible initial string before operations.

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

Note:
In the first sample, you can transform ")((())))" into ")(()(())))" by splitting it into ")(", empty string, and "(())))". It can be shown that this is the lexicographically smallest possible initial string

Example input:
)(()(())))

Example output:
)((())))

Editorial:
Make a rooted tree. Each suffix has a node and except for the root, each node belongs to a suffix. Each edge has a character written on it. "(" or ")"
The answer for each suffix can be obtained by moving up from it's node to the root and concatenating the characters. (kind of like an upside-down Trie)
Now we need to be able to compare answers of two suffixes.
For each node $$$v$$$ and for each $$$i \le \log(n)$$$ store hash of the path of $$$v$$$ to it's $$$2^i$$$-th ancestor in $$$h[v][i]$$$.
In order to compare two nodes $$$v$$$ and $$$u$$$, find the smallest $$$i$$$ that the $$$i$$$-th character of them differ. Then we can determine which one is lexicographically smaller. And we use binary lifting to find that $$$i$$$.
The root of the tree is called node $$$n + 1$$$.
• Iterate $$$i$$$ in decreasing order.
• Assign node $$$i + 1$$$ to be the parent of node $$$i$$$.
• If currently $$$ans_i < ans_{nxt_i}$$$, assign $$$nxt_i$$$'s parent to be $$$i$$$'s parent with the same edge character as $$$nxt_i$$$. (You could also make $$$nxt_i$$$ to present both of them. In order to do this, for each suffix you need to store which node is storing it's answer.)
And then you have calculate the answer by moving up the tree.
Time complexity: $$$\mathcal{O}(n\log n)$$$