Codeforces 381E Sereja and Brackets（线段树）

80 阅读 0 评论 53 点赞

我是靠谱客的博主温暖小天鹅，最近开发中收集的这篇文章主要介绍Codeforces 381E Sereja and Brackets（线段树），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://codeforces.com/contest/381/problem/E

             Sereja and Brackets

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 ≤ 10^6) 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 test(s)
Input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Output

0
0
2
10
4
6
6

题意是在给出的[l,r]区间内判断已经匹配的括号数。
N有1e6的大小，用DP显然是不可能的。
于是想到用线段树。
线段树中用结构体存储，结构体中有ans（在该区间内的括号匹配数），a（该区间内‘（’未被匹配数），b（该区间内‘）’未被匹配数）。
然后区间合并的时候，取
t=min（tr[i<<1].a, tr[i<<1|1].b);
tr[i].a = tr[i<<1].a + tr[i<<1|1].a - t;
tr[i].b = tr[i<<1].b +tr[i<<1|1].b - t;
tr[i].ans = tr[i<<1].ans +tr[i<<1|1].ans + t *2;

在query的时候也要注意一下是否有新的括号匹配。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdlib>

#define lson  l,mid,i<<1
#define rson  mid+1,r,i<<1|1
using namespace std;

const int N = 1e6 + 100;

struct Node
{
    int ans;
    int a;
    int b;
}tr[N*4];

char str[N];
int n,res,now;

void built(int l,int r,int i)
{
    if(l==r)
    {
        if(str[l-1]=='(') tr[i].a++;
        else tr[i].b ++;

        tr[i].ans = 0;
        return;
    } 

    int mid = (l+r)/2;
    built(lson);
    built(rson);

    int xx = min(tr[i<<1].a,tr[i<<1|1].b);
    tr[i].a = tr[i<<1].a + tr[i<<1|1].a - xx;
    tr[i].b = tr[i<<1].b + tr[i<<1|1].b - xx;
    tr[i].ans = tr[i<<1].ans + tr[i<<1|1].ans + xx*2;

    return ;
}

void query(int l,int r,int i,int a,int b)
{
    if(l>=a && r<=b)
    {
        res += tr[i].ans;
        int x = min(now,tr[i].b);
        res += x*2;
        now = now + tr[i].a - x;
        return; 
    }

    int mid = (l+r)>>1;
    if(mid>=a) query(lson,a,b);
    if(mid<b) query(rson,a,b);
    return;
}
int main()
{
    gets(str);
    n = strlen(str);
    built(1,n,1);

    int m;
    scanf("%d",&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        res = 0;
        now = 0;
        query(1,n,1,x,y);
        printf("%dn",res);
    }
    return 0;
}