首页 > 代码库 > CodeForces 380C Sereja and Brackets（扫描线+树状数组）
CodeForces 380C Sereja and Brackets（扫描线+树状数组）
【题目链接】 http://codeforces.com/problemset/problem/380/C
【题目大意】
给出一个括号序列，求区间内左右括号匹配的个数。
【题解】
我们发现对于每个右括号，其匹配的左括号是固定的，
我们保存每个右括号匹配的左括号位置，
对区间询问进行线扫描，将扫描的区间右端点及其之前所有的右括号对应的左括号位置做标记，
只要查询询问区间的标记个数就是答案，这个可以用树状数组维护。
【代码】
#include <cstdio>#include <algorithm>#include <cmath>#include <cstring> const int N=1000010;using namespace std;typedef long long LL;int i,n,m,ans,res[N],c[N];struct Q{int l,r,id;}ask[N];bool cmp(Q a,Q b){return a.r<b.r;}int st[N],top,pre[N];char s[N];int main(){ while(~scanf("%s",s+1)){ memset(c,0,sizeof(c)); memset(res,0,sizeof(res)); n=strlen(s+1); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].id=i; top=0; for(int i=1;i<=n;i++){ if(s[i]==‘(‘)st[++top]=i; else pre[i]=top?st[top--]:n+1; }sort(ask+1,ask+m+1,cmp); int pos=0; for(int i=1;i<=m;i++){ while(pos<ask[i].r){pos++;if(s[pos]==‘)‘)for(int x=pre[pos];x<=n;x+=x&-x)c[x]++;} for(int x=ask[i].r;x;x-=x&-x)res[ask[i].id]+=c[x]; for(int x=ask[i].l-1;x;x-=x&-x)res[ask[i].id]-=c[x]; }for(int i=1;i<=m;i++)printf("%d\n",res[i]<<1); }return 0;}CodeForces 380C Sereja and Brackets（扫描线+树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。