Easy Sequence
Description:
soda has a string containing only two characters -- '(' and ')'. For every character in the string, soda wants to know the number of valid substrings which contain that character.
Note:
An empty string is valid. If S is valid, (S) is valid. If U,V are valid, UV is valid.
Note:
An empty string is valid. If S is valid, (S) is valid. If U,V are valid, UV is valid.
Input:
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
A string s consisting of '(' or ')' (1≤|s|≤106).
Output:
For each test case, output an integer m=
where ansi is the number of valid substrings which contain i-th character.
Sample Input:
2 ()() ((()))
Sample Output:
20 42
Hint:
For the second case, ans={1,2,3,3,2,1}, then m=1⋅1+2⋅2+3⋅3+4⋅3+5⋅2+6⋅1=42
Source:
Submit