1 second
256 megabytes
standard input
standard output
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.
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.
Print the answer to each question on a single line. Print the answers in the order they go in the input.
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
0
0
2
10
4
6
6
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 «()(())(())».
题意：给你一个括号序列，q个询问，求区间内括号匹配的数量；
思路：线段数区间合并；
一个线段树存三个数，l,m,r;
l表示区间内除去以匹配的左括号的数量；
r表示区间内除去以匹配的右括号的数量；
m表示匹配好的左右括号的数量；
对于左边的区间，和右边的区间，只要将 左边的l和右边的尽量匹配即可；
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e6+,M=1e7+,inf=1e9+;
const ll INF=1e18+,mod=1e9+; /// 数组大小
char s[N]; struct ans
{
int x,y,z;
ans(){}
ans(int xx,int yy,int zz)
{
x=xx;y=yy;z=zz;
}
}; struct SGT
{
int LT[N<<],RT[N<<],MT[N<<];
void pushup(int pos)
{
int k=min(LT[pos<<],RT[pos<<|]);
MT[pos]=MT[pos<<]+MT[pos<<|]+*k;
LT[pos]=LT[pos<<]+LT[pos<<|]-k;
RT[pos]=RT[pos<<]+RT[pos<<|]-k;
}
void build(int l,int r,int pos)
{
if(l==r)
{
LT[pos]=;
RT[pos]=;
MT[pos]=;
if(s[l]=='(')
LT[pos]++;
else
RT[pos]++;
return;
}
int mid=(l+r)>>;
build(l,mid,pos<<);
build(mid+,r,pos<<|);
pushup(pos);
}
ans query(int L,int R,int l,int r,int pos)
{
if(L==l&&r==R)
return ans(LT[pos],MT[pos],RT[pos]);
int mid=(l+r)>>;
if(R<=mid)
return query(L,R,l,mid,pos<<);
else if(L>mid)
return query(L,R,mid+,r,pos<<|);
else
{
ans a=query(L,mid,l,mid,pos<<);
ans b=query(mid+,R,mid+,r,pos<<|);
int k=min(a.x,b.z);
int m=a.y+b.y+*k;
int l=a.x+b.x-k;
int r=a.z+b.z-k;
return ans(l,m,r);
}
}
};
SGT tree;
int main()
{
scanf("%s",s+);
int x=strlen(s+);
tree.build(,x,);
int q;
scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",tree.query(l,r,,x,).y);
}
return ;
}
/*
))(()))))())())))))())((()()))))()))))))))))))
9
26 42
21 22
6 22
7 26
43 46
25 27
32 39
22 40
2 45
*/