Description
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.
Input
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.
Output
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
Note
A subsequence of length |x| of string s = s1s2... s|s| (where |s| is the length of string s) is string x = sk1sk2... sk|x| (1 ≤ k1 < k2 < ... < k|x| ≤ |s|).
A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.
For the third query required sequence will be «()».
For the fourth query required sequence will be «()(())(())».
解题思路：求连续子串中括号匹配的个数。括号匹配问题一般可以用栈来维护。对于每个右括号，其匹配的左括号是固定的，因此我们可以记录每个右括号匹配的左括号位置，对整个区间进行线扫描，同时用树状数组维护+离散化处理即可。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=1e6+5; 5 const int maxv=1e5+5; 6 char str[maxn];int n,m,pos,tree[maxn],ans[maxv];stack<int> st; 7 struct node{int l,r,id;}query[maxn]; 8 bool cmp(node a,node b){return a.r<b.r;}///右端点排序 9 inline int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 inline void print(int x){ 16 if(x<0)putchar('-'),x=-x; 17 if(x>9)print(x/10); 18 putchar(x%10+'0'); 19 } 20 int lowbit(int x){return x&-x;} 21 void add(int x,int val){ 22 for(int i=x;i<=n;i+=lowbit(i))tree[i]+=val; 23 } 24 int get_sum(int x){ 25 int ans=0; 26 for(int i=x;i>0;i-=lowbit(i))ans+=tree[i]; 27 return ans; 28 } 29 int main(){ 30 while(~scanf("%s",str)){ 31 while(!st.empty())st.pop();n=strlen(str); 32 memset(tree,0,sizeof(tree)),memset(ans,0,sizeof(ans));m=read(); 33 for(int i=0;i<m;++i)query[i].l=read(),query[i].r=read(),query[i].id=i; 34 sort(query,query+m,cmp);pos=1; 35 for(int i=0;i<m;++i){ 36 for(int j=pos;j<=query[i].r;++j){ 37 if(str[j-1]=='(')st.push(j);///记录左括号的位置（物理位置） 38 else if(!st.empty())add(st.top(),2),st.pop();///单点更新 39 } 40 pos=query[i].r+1;///从下一个位置开始，避免重叠，O(n)遍历 41 ans[query[i].id]=get_sum(query[i].r)-get_sum(query[i].l-1); 42 } 43 for(int i=0;i<m;++i)print(ans[i]),puts(""); 44 } 45 return 0; 46 }