首页 > 代码库 > Codeforces 380C. Sereja and Brackets【线段树】

Codeforces 380C. Sereja and Brackets【线段树】

2024-07-20 06:38:50   222人阅读

题目大意：

给出一串括号，有m个查询（包含a,b）问区间[a,b]之间有多少个匹配的括号

做法：

处理两个数组r[i](代表从1到i之间有多少个已匹配的右括号),l[i](代表从1到i之间有多少个没有匹配的左括号)。我们要算[a,b]之间的匹配的括号数，首先用r[b]-r[a-1]，但是遮掩更有可能a到b之间的右括号是在[1,a-1]之间被匹配的，那么再减去l[a-1],但是减去的这一部分中，也有可能是在[b+1,len]这个区间中被匹配，要加上这一部分不该减去的数值，那么只需要在加上min(l[a]~l[b])即可。区间最小值，那就用线段树吧

代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 1000010
using namespace std;
#define L(x) (x)<<1
#define R(x) (x)<<1|1
int m,len,r[N],l[N];
char bra[N];
struct node
{
    int ll,rr,v;
}t[N*6];
int bulid(int x,int y,int idx)
{
    t[idx].ll=x,t[idx].rr=y;
    if(x==y) return t[idx].v=l[x];
    int mid=(x+y)/2;
    return t[idx].v=min(bulid(x,mid,L(idx)),bulid(mid+1,y,R(idx)));
}
int query(int x,int y,int idx)
{
    if(x==t[idx].ll && y==t[idx].rr) return t[idx].v;
    int mid=(t[idx].ll+t[idx].rr)/2;
    if(x>mid) return query(x,y,R(idx));
    if(y<=mid) return query(x,y,L(idx));
    return min(query(x,mid,L(idx)),query(mid+1,y,R(idx)));
}
int main()
{
    scanf("%s",bra);
    len=strlen(bra);
    int tmp=0;
    for(int i=1;i<=len;i++)
    {
        r[i]=r[i-1];
        if(bra[i-1]=='(') tmp++;
        else if(tmp) r[i]++,tmp--;
        l[i]=tmp;
    }
    bulid(1,len,1);
    scanf("%d",&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==b) {cout<<0<<endl;continue;}
        int ans=min(r[b]-r[a-1],r[b]-r[a-1]-l[a-1]+query(a,b,1));
        cout<<ans*2<<endl;
    }
    return 0;
}


Codeforces 380C. Sereja and Brackets【线段树】


联系
我们