你可以手画一下,然后发现求的其实就是 $[l,r]$ 区间内合法序列匹配个数.
用线段树维护一下括号序列就可以了.
code:
#include <bits/stdc++.h> #define N 1000005 #define ll long long #define lson now<<1 #define rson now<<1|1 #define setIO(s) freopen(s".in","r",stdin) using namespace std; struct node { int sum,ans,mi,ma; node() { sum=ans=mi=ma=0; } node operator+(const node &b) const { node c; c.sum=sum+b.sum; c.ans=ans+b.ans+min(ma,-b.mi); c.mi=min(mi,sum+b.mi); c.ma=max(b.ma,ma+b.sum); return c; } }s[N<<2]; char str[N]; void build(int l,int r,int now) { if(l==r) { if(str[l]=='(') s[now].sum=1,s[now].ma=1; else s[now].sum=-1,s[now].mi=-1; return; } int mid=(l+r)>>1; build(l,mid,lson),build(mid+1,r,rson); s[now]=s[lson]+s[rson]; } node query(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) return s[now]; int mid=(l+r)>>1; if(L<=mid&&R>mid) return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R); else if(L<=mid) return query(l,mid,lson,L,R); else return query(mid+1,r,rson,L,R); } int main() { // setIO("input"); int i,j,n,Q; scanf("%s%d",str+1,&Q); n=strlen(str+1),build(1,n,1); for(i=1;i<=Q;++i) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",query(1,n,1,l,r).ans<<1); } return 0; }