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?≤?106) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1?≤?m?≤?105) — 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.
())(())(())( 7 1 1 2 3 1 2 1 12 8 12 5 11 2 10
0 0 2 10 4 6 6
题意：给定一组括号，以下有m次询问，问一个区间有几个括号匹配。
思路：线段树，在向上传递值的时候，左区间的左括号和右区间的右括号能组成一个新括号传递上去。
代码：
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 1000005;
int n, m;
char str[N];
struct Tree {
int l, r, lv, rv, sum;
Tree operator + (const Tree &a) {
Tree h;
h.sum = sum + a.sum; h.lv = lv + a.lv; h.rv = rv + a.rv;
int num1 = min(lv, a.rv);
h.sum += num1 * 2; h.lv -= num1; h.rv -= num1;
return h;
}
}st[3 * N];
Tree build(int l, int r, int id) {
if (l == r) {
if (str[l] == ‘(‘) {
st[id].lv = 1; st[id].rv = 0; st[id].sum = 0;
}
else {
st[id].lv = 0; st[id].rv = 1; st[id].sum = 0;
}
st[id].l = l; st[id].r = r;
}
else {
int mid = (l + r) / 2;
st[id] = build(l, mid, id * 2) + build(mid + 1, r, id * 2 + 1);
st[id].l = l; st[id].r = r;
}
return st[id];
}
Tree Query(int l, int r, int id) {
if (l == st[id].l && r == st[id].r)
return st[id];
int mid = (st[id].l + st[id].r) / 2;
if (l <= mid && r > mid)
return Query(l, mid, 2 * id) + Query(mid + 1, r, 2 * id + 1);
else if (l <= mid && r <= mid) {return Query(l, r, 2 * id);}
else {return Query(l, r, 2 * id + 1);}
}
void init() {
scanf("%s%d", str + 1, &m);
n = strlen(str + 1);
build(1, n, 1);
int l, r;
while (m--) {
scanf("%d%d", &l, &r);
printf("%d\n", Query(l, r, 1).sum);
}
}
int main() {
init();
return 0;
}