我们将使用线段树来维护。在每个节点处存储以下信息：

• $a_v$ —— 该区间内最长正确括号子序列的长度
• $b_v$ —— 该区间内未被匹配的开括号 '(' 的数量
• $c_v$ —— 该区间内未被匹配的闭括号 ')' 的数量

如果我们想要合并两个节点，其参数分别为 $(a_1, b_1, c_1)$ 和 $(a_2, b_2, c_2)$，可以使用以下规则：

• $t = \min(b_1, c_2)$
• $a = a_1 + a_2 + t \times 2$
• $b = b_1 + b_2 - t$
• $c = c_1 + c_2 - t$

注意：原公式中 $a = a_1 + a_2 + t$ 仅计算了“匹配的对数”，最终实际长度应为 $a \times 2$。原代码实现中通常以“对数”存储，或者最后乘以 $2$，请根据实现调整。

#include<bits/stdc++.h>
using namespace std;
struct A{
int a;
int b;
int c;
};
vector<A> v;
string s;

A combine(A l,A r){
int t=min(l.b,r.c);
return {l.a+r.a+t,l.b+r.b-t,l.c+r.c-t};
}
void build(int t,int l ,int r){
if(l==r){
if(s[l]=='('){
 v[t]={0,1,0};
 }
else{
 v[t]=A{0,0,1};
}
return;
}
int mid =(l+r)/2;
build(2*t,l,mid);
build(2*t+1,mid+1,r);
v[t]=combine(v[2*t],v[2*t+1]);
}
A query(int t,int tl,int tr,int l,int r){
if(l>r){return{0,0,0};}
if(tl==l&&tr==r){return v[t];}
int tmid=(tl+tr)/2;
A a=query(t*2,tl,tmid,l,min(r,tmid));
A b=query(t*2+1,tmid+1,tr,max(l,tmid+1),r);
return combine(a,b);
}

int main(){

cin>>s;
v.resize(4*s.length());
build(1,0,s.length()-1);
int m;
cin>>m;
int l,r;
while(m--){
cin>>l>>r;
cout<<query(1,0,s.length()-1,l-1,r-1).a*2<<"\n";
}
}