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

help
, , , ,
1

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 : “Problem - C - Codeforces” [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 .

2

Give some initial idea I will try .

3

(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

4

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

1 Like
5

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

6

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

Here my submission for CF : “Submission #92021947 - Codeforces”

7

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.

8

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

9

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
10

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

11

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
12

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

13

sorry my bad.