Range Queries for Longest Correct Bracket Substring [ BIT ,Segment Tree ]

Given a string S , of length N (contains parenthesis ) , and Q queries, in each query L and R be two indexes of string find the length of the longest balanced substring between L to R.

Ex : S = ( ( ) ) ( ) ( ) ( ( ( )

Q = 2

L = 1 , R = 4 answer = 4
L = 4 , R = 9 answer = 4

Help @galencolin @everule1 @chaudhary_19 @aneee004 @udayan14 @spaanse @ay2306 @ssjgz @dvyn01 @souradeep1999 @samarth2017
How to solve this using BIT .

I solved this : “https://codeforces.com/contest/380/problem/C” [Subsequence] , but don’t know how to solve above ?

And If anyone find out same question above then please share , as I google and only find subsequence variant .

Give some initial idea I will try .

(Actually, you have tagged a noob between legends…XD) btw can you give me little insights about how you solved this cf problem, I mean just give hints, phle khud try krna hai, editorial baad me dekhunga

for each closing bracket find its last matching opening bracket . and then process query in sorting manner of “r”.

1 Like

Is this the answer? Seems nice. Sorry I thought you found answer and wrote it. I am curious as well.

No this is the answer for cf version , I need answer / approach for my above question -

Here my submission for CF : “https://codeforces.com/contest/380/submission/92021947

I think I might have an idea, consider F(i) = count['('] - count[')'] in S[0...i]

Now for any substring (i,j] to be valid following condition must hold true F(i) = F(j)

I think we may try to build answer from this observation. If I will find something more, I will update this comment.

Yes , and if u found same question please let me know.

No, assume S = ))((, F(0) = -1, F(1) = -2, F(2) = -1, then F(0) = F(2) but (0, 2] is not balanced.

1 Like

if f(i) == f(j) for any i<j then sub-string (i,j] will hold if s[i+1]==’(’.

No, assume S = )())(, F(0) = -1, F(1) = 0, F(2) = -1, F(3) = -2, F(4) = -1, again F(0) = F(4) but (0, 4] is not balanced.
Next time, come with a mathematical proof of what you say.

1 Like

Is this an actual question? I don’t think you can get better than mo’s algorithm, which already has a quite complex transition.

Also @tushar2018, it holds if f(i)=f(j) and for all i < k< j, f(k) \ge f(i).

sorry my bad.