You are not logged in. Please login at www.codechef.com to post your questions!

×

LBRACKET - Editorial

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.

asked 03 Oct '16, 22:05

gvaibhav21's gravatar image

7★gvaibhav21
947210
accept rate: 25%

edited 03 Oct '16, 22:23

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,679
×1,755
×1,404
×1,250

question asked: 03 Oct '16, 22:05

question was seen: 1,029 times

last updated: 03 Oct '16, 22:23