题意：
给出一串括号
给出一些询问，问某个区间[l,r]内的能合法匹配的括号数有多少个
分析：
我们能够实现处理两个数组
sum[i] 1....i中已经能匹配的右括号的数目
left[i] 1....i中还不能匹配的左括号数目
这两个数组能够非常easy的扫描一遍动态维护得出来
我们能够先求前缀和，即
1...m中有多少能匹配的右括号sum[m]
则，我们能够得到sum[r]-sum[l-1]，区间[l,r]内能合法匹配的右括号
可是这些右括号的匹配包含了和[1,l-1]中的左括号的匹配
所以我们再减去left[l-1]。可是
这又会多减去了[1,l-1]中和[r+1....]右括号匹配的左括号
所以得加上这部分
这部分是多少？这是这个问题的关键也是这个问题比較难以理解的地方
这部分是min(left[l]...left[r])
为什么？
…...(..(.......
.....)......(............ ..)........)
1 2 L 3 4 R 5 6
红色部分是询问区间L,R
能够看出
我们这里减去了1,2括号
然而括号1是不应该减去的，它和括号6配对
括号2是应该减去的。它和括号3配对
假设我们取L，R上left的最小值，那么能够看到最小值落在括号3和括号4之间，能够避免把括号4算入（它和括号5匹配）
并且也能够把多减掉的括号1给加上
然而这里另一个tricks，假设，类似4号括号的这种括号在L,R区间上第一个位置的时候，这里是没有min的位置的。
推断这样的情况也确实麻烦
我们作例如以下处理
假设 left[l-1]-min(left[l]...left[r])<0则不减。否则减去（由于L，R内能匹配的右括号不超过sum[r]-sum[l-1]，后者中的右括号还能和1。L上的左括号匹配）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
const int NN=1111111;
char str[NN];
char tmp[NN];
int l[NN],r[NN];
struct TREE{
int x;
}tr[NN*6];
void build(int idx,int L,int R){
if(L==R){
tr[idx].x=l[L];
return;
}
int mid=(L+R)/2;
build(L(idx),L,mid);
build(R(idx),mid+1,R);
tr[idx].x=min(tr[L(idx)].x,tr[R(idx)].x);
}
int que(int idx,int ll,int rr,int L,int R){
int mid=(L+R)/2;
if(ll==L && rr==R){
return tr[idx].x;
}
if(rr<=mid){
return que(L(idx),ll,rr,L,mid);
}else if(ll>=mid+1){
return que(R(idx),ll,rr,mid+1,R);
}else{
return min(que(L(idx),ll,mid,L,mid),que(R(idx),mid+1,rr,mid+1,R));
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("G:/in.txt","r",stdin);
//freopen("G:/myout.txt","w",stdout);
#endif
cin>>(str+1);
//cin>>tmp;
int n;cin>>n;
int len=strlen(str+1);
for(int i=1;i<=len;i++){
l[i]=l[i-1];
r[i]=r[i-1];
if(str[i]=='('){
l[i]++;
}else{
if(l[i]){
l[i]--;
r[i]++;
}
}
}
build(1,1,len);
while(n--){
int x,y;cin>>x>>y;
if(x==y){
cout<<0<<endl;
continue;
}
int ans=r[y]-r[x-1];
ans-=max(0,l[x-1]-que(1,x,y,1,len));
cout<<ans*2<<endl;
}
}