Problem Idea #3: Correct Bracket Sequence

general
1

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.

Note:

A Correct Bracket Sequence (CBS) is a sequence that can be obtained through following rules:

  1. An empty string is a CBS.

  2. If A is a CBS, then B = (A) is also a CBS.

  3. If A and B are CBS, then C = AB is also a CBS.

N <= 10^6 , Q <= 10^6 ( or maybe Test cases <= 10 and N <= 10^5 , Q <= 10^5 )