【题意】给一个括号字符串，然后m个查询，查询【L,R】区间里最大的括号匹配数。

【解题方法】虽然是E题，但我不得不说这是个很水的题。我们只需要考虑一下每个区间没匹配左括号的个数，没匹配的右括号的个数，以及匹配的括号数即可。接下来就是区间合并的典型套路了。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
char s[maxn];
struct node{
    int l,r;
    int a,b,ans;
}Tree[maxn<<2];
void pushup(int rt){
    int tt=min(Tree[rt*2].a,Tree[rt*2+1].b);
    Tree[rt].a=Tree[rt*2].a+Tree[rt*2+1].a-tt;
    Tree[rt].b=Tree[rt*2].b+Tree[rt*2+1].b-tt;
    Tree[rt].ans=Tree[rt*2].ans+Tree[rt*2+1].ans+tt*2;
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r;
    if(l==r){
        if(s[l-1]=='(') Tree[rt].a++;
        else Tree[rt].b++;
        Tree[rt].ans=0;
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
int ans,now;
node queryans(int L,int R,int rt){
    if(L==Tree[rt].l&&Tree[rt].r==R){
        return Tree[rt];
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) return queryans(L,R,rt*2);
    else if(L>mid) return queryans(L,R,rt*2+1);
    else{
        node as;
        node as1=queryans(L,mid,rt*2);
        node as2=queryans(mid+1,R,rt*2+1);
        int tt=min(as1.a,as2.b);
        as.a=as1.a+as2.a-tt;
        as.b=as1.b+as2.b-tt;
        as.ans=as1.ans+as2.ans+tt*2;
        return as;
    }
}
int main(){
    cin>>s;
    int n=strlen(s);
    Build(1,n,1);
    int q,l,r;
    cin>>q;
    for(int i=1; i<=q; i++){
        cin>>l>>r;
        node tmp=queryans(l,r,1);
        cout<<tmp.ans<<endl;
    }
}