LBRACKET - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Vaibhav Gosain

Editorialist: Vaibhav Gosain

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Segment Trees

PROBLEM:

Given a string containing only ‘(’ and ‘)’, you have to handle 2 types of operations on it:

  1. 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 ‘(’ ).

  2. 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.

EXPLANATION:

Can be solved via segment tree:

Things to maintain at every segment tree node:

  1. Prefix sum parenthesis [+1 for ( and -1 for ) ] before the starting position of current range (denote it by pre)
  2. Sum of parenthesis for current range.
  3. Minimum value of prefix sum at any position in range.
  4. Maximum value of prefix sum at any position in range.
  5. Lazy Count of flips not propagated to children
  6. 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:

Author’s solution can be found here.