Peter and Bracket Matching
All submissions for this problem are available.
Peter and Ivan, being programmers, love brackets. One day Peter challenged Ivan to solve a problem to see whose love is greater. The problem is to efficiently perform the following task.
Given a sequence of brackets ‘(‘ and ‘)’ of length N and Q queries. Each of the query is the following form.
1 p x: insert a bracket x at position p. x is either ‘(’ or ‘)’
2 l r: reverse the bracket sequence from position [l, r] i.e A[l+k] becomes A[r-k] for all k in range [0, r-l]
3 l r: Count the number of distinct balanced bracket sequences that can be formed by using brackets from l to r (possibly not all) mod 10^9+7. Remember: A balanced bracket sequence is one where number of opening brackets is equal to the number of closing brackets and for every prefix of the sequence the no of opening brackets is greater than or equal to the number of closing brackets.
Note: You can rearrange the brackets for query of type 3 for forming sequences. However the array has to be left unchanged by this query.
Despite all his skills, Ivan finds himself unable to solve the problem efficiently. Ivan hates loosing. Therefore he asks you for your help. Help Ivan solve it otherwise he will loose the bet.
The first line will consist of string S containing a bracket sequence and an positive integer Q. It is followed by Q queries as mentioned in the problem. All indices are 1-based.
For each query of type 3, print the number of balanced bracket sequences that can be formed using the brackets.
- 1 <= |S| <= 105
- 1 <= Q <= 105
3 1 2
3 1 3
1 1 )
3 1 4
2 1 3
3 1 2
Query #1: The only balanced sequence is ‘()’
Query #2: The only balanced sequence is ‘()’
After the insertion operation the bracket sequence becomes )()(
Query #3: The only balanced sequence is ‘()’, ‘(())’, ‘()()’
After the reverse operation the bracket sequence becomes )()(
Query #4: The only balanced sequence is ‘()’
|Time Limit:||- 1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions