You have a bracket sequence of length . Answer queries: for substring , find the length of the longest valid bracket subsequence.
A valid bracket sequence has matching pairs. For example, in "(())()", the whole string is valid with length .
Constraints: . You need per query, which means segment tree.
Checking each query by scanning takes per query. With queries, this is too slow. Use a segment tree with custom merge. Uses space for the tree.