BALANCE1PARA - Balance the parentheses
You are provided with a sequence of parentheses, that are balanced. A balanced parentheses sequence it that sequence in which every opening bracket has a unique closing bracket (nearest to it) to the right of it and every closing bracket has a unique opening bracket to the left of it (nearest). Any other sequence is not balanced. For example, (()), ()(), ((()())()), (), etc are balanced, but )(), ()), (()(, ()( are unbalanced.
You are then provided with q queries, ith query is of form xi, , representing an index. the bracket at that index is flipped that is, if it was an opening bracket then it is replaced by a closing one and vice versa. You have to give the left most index whose bracket has to be flipped so that the sequence remains balanced. The subsequent queries have to be applied on new sequence formed!
Input
The first line will contain two integers, n and q. Next line will give you the sequence (n characters) consisting of opening and closing parenthesis only. Next q lines will represent q queries, xi.
Output
For each query, output the required answer in different lines.
Constraints
1<=n<=4*10^5
1<=q<=2*10^5
Example
Input: 10 10 ()(((()))) 2 7 9 4 5 1 4 3 5 4 Output: 2 4 6 4 2 1 2 2 4 4
Input: 6 9 ((())) 6 2 2 6 4 6 3 2 4 Output: 6 2 2 6 2 6 2 2 3
hide comments
manish556:
2016-08-31 17:09:13
what should be the time comlexity of the solution to be accepted? |
|
square1001:
2016-08-18 06:20:50
[Hidden]
|
Added by: | Abhinandan Agarwal |
Date: | 2016-08-17 |
Time limit: | 3.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | ICPC-ASIA-TOKYO Regionals |