Codeforces 380C Sereja and Brackets - Problem Statement

You have a bracket sequence of length $n$. Answer $m$ queries: for substring $[l, r]$, 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 $6$.

Constraints: $n, m \le 10^6$. You need $O(\log n)$ per query, which means segment tree.

Checking each query by scanning takes $O(n)$ per query. With $m$ queries, this is too slow. Use a segment tree with custom merge. Uses $O(n)$ space for the tree.