首页 > 代码库 > codeforces 380C 线段树括号匹配

codeforces 380C 线段树括号匹配

2024-08-08 06:10:22   219人阅读

Sereja and Brackets
Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit Status

Description

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.

Input

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.

Output

Print the answer to each question on a single line. Print the answers in the order they go in the input.

Sample Input

Input
())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10
Output
0
0
2
10
4
6
6

Hint

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 ?()(())(())?.

给出一段序列，问在这段序列中有几对完整的括号匹配
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 1111111
using namespace std;
struct Node
{
    int l,r,all;
    Node()
    {
        l=r=all=0;
    }
    Node(int a,int b,int c)
    {
        l=a,r=b,all=c;
    }
};
Node sum[MAXN<<2];
char str[MAXN];
void pushup(int rt)
{
    int t=min(sum[rt<<1].l,sum[rt<<1|1].r);
    sum[rt].all=sum[rt<<1].all+sum[rt<<1|1].all+t;
    sum[rt].l=sum[rt<<1].l+sum[rt<<1|1].l-t;
    sum[rt].r=sum[rt<<1].r+sum[rt<<1|1].r-t;
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        if(str[l]=='(')
            sum[rt].l++;
        else if(str[l]==')')
            sum[rt].r++;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
Node query(int l,int r,int L,int R,int rt)
{
    if(l>=L&&R>=r)
        return sum[rt];
    Node cnt1,cnt2;
    int mid=(l+r)>>1;
    if(L<=mid)
        cnt1=query(l,mid,L,R,rt<<1);
    if(R>mid)
        cnt2=query(mid+1,r,L,R,rt<<1|1);
    int t=min(cnt1.l,cnt2.r);
    return Node(cnt1.l+cnt2.l-t,cnt1.r+cnt2.r-t,cnt1.all+cnt2.all+t);
}
int main()
{
    int q,l,r;
    scanf("%s",str+1);
    scanf("%d",&q);
    int n=strlen(str+1);
    build(1,n,1);
    while(q--)
    {
        scanf("%d %d",&l,&r);
        printf("%d\n",2*query(1,n,l,r,1).all);
    }
    return 0;
}


codeforces 380C 线段树括号匹配


联系
我们