CF 380C - tacongnam/DylanHarris GitHub Wiki
- Problem: CODEFORCES - 380C
- Tag: Graph - Segment Tree
- Name: Sereja and Brackets
- Introduction:
Time limit per test: 1 second
Memory limit per test: 256 megabytes
Input: standard input
Output: standard output
Sereja has a bracket sequence s1, s2, ..., sn, or, in other words, a string s of length n, consisting of characters "(" and ")".
Sereja needs to answer m queries, each of them is described by two integers li, ri (1 ≤ li ≤ ri ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence sli, sli + 1, ..., sri. Help Sereja answer all queries.
You can find the definitions for a subsequence and a correct bracket sequence in the notes.
The first line contains a sequence of characters s1, s2, ..., sn (1 ≤ n ≤ 10^6) without any spaces. Each character is either a "(" or a ")".
The second line contains integer m (1 ≤ m ≤ 10^5) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n) — the description of the i-th query.
Print the answer to each question on a single line. Print the answers in the order they go in the input.
Input:
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
Output:
0
0
2
10
4
6
6
We will support the segments tree. At each vertex will be stored:
a[v] — the maximum length of the bracket subsequence
b[v] — how many there it open brackets that sequence doesn't contain
c[v] — how many there it closed brackets that sequence doesn't contain
If we want to combine two vertices with parameters (a1, b1, c1) and (a2, b2, c2), we can use the following rules:
t = min(b1, c2)
a = a1 + a2 + t
b = b1 + b2 - t
c = c1 + c2 - t