Author: Vaibhav Gosain
Editorialist: Vaibhav Gosain
Given a string containing only ‘(’ and ‘)’, you have to handle 2 types of operations on it:
update x,y: flip all parenthesis in the string lying between x to y (both inclusive) (all occurrences of ‘(’ are replaced with ‘)’ and all occurences of ‘)’ are replaced with ‘(’ ).
query x: find the longest contiguous correct bracket sequence starting from position x.
The length of the string is N , and you have to handle Q operations.
Can be solved via segment tree:
Things to maintain at every segment tree node:
- Prefix sum parenthesis [+1 for ( and -1 for ) ] before the starting position of current range (denote it by pre)
- Sum of parenthesis for current range.
- Minimum value of prefix sum at any position in range.
- Maximum value of prefix sum at any position in range.
- Lazy Count of flips not propagated to children
- Lazy prefix sum not yet added to current node
Using these, we can perform range_flip operation in O(logN) per query. You can refer to the Author’s solution for more details: Link
For query 2 x we need to find first position greater than (x-1) with prefix sum less than the prefix sum at position (x-1). When we range query in a segment tree, it is divided into O(logN) complete node ranges. Find the first range from the left side which has range minimum less than prefix sum at x-1. We can now find the first point in that range with the required prefix sum.
Time Complexity: O((N+Q)*log(N))
Author’s solution can be found here.