首页 > 代码库 > CF380C Sereja and Brackets [想法+线段树]

CF380C Sereja and Brackets [想法+线段树]

题意:

给出一串括号

给出一些询问,问某个区间[l,r]内的能合法匹配的括号数有多少个


分析:

我们可以实现处理两个数组

sum[i] 1....i中已经能匹配的右括号的数目

left[i] 1....i中还不能匹配的左括号数目

这两个数组可以很简单的扫描一遍动态维护得出来


我们可以先求前缀和,即

1...m中有多少能匹配的右括号sum[m]

则,我们可以得到sum[r]-sum[l-1],区间[l,r]内能合法匹配的右括号

但是这些右括号的匹配包括了和[1,l-1]中的左括号的匹配

所以我们再减去left[l-1],但是

这又会多减去了[1,l-1]中和[r+1....]右括号匹配的左括号

所以得加上这部分


这部分是多少?这是这个问题的关键也是这个问题比较难以理解的地方


这部分是min(left[l]...left[r])为什么?


...(..(............)......(............ ..)........)

  1 2        L  3     4           R 5       6

红色部分是询问区间L,R

可以看出

我们这里减去了1,2括号

然而括号1是不应该减去的,它和括号6配对

括号2是应该减去的,它和括号3配对


如果我们取L,R上left的最小值,那么可以看到最小值落在括号3和括号4之间,可以避免把括号4算入(它和括号5匹配)

而且也可以把多减掉的括号1给加上



然而这里还有一个tricks,如果,类似4号括号的这样的括号在L,R区间上第一个位置的时候,这里是没有min的位置的。

判断这种情况也确实麻烦

我们作如下处理

如果 left[l-1]-min(left[l]...left[r])<0则不减,否则减去(因为L,R内能匹配的右括号不超过sum[r]-sum[l-1],后者中的右括号还能和1,L上的左括号匹配)


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
const int NN=1111111;
char str[NN];
char tmp[NN];
int l[NN],r[NN];
struct TREE{
	int x;
}tr[NN*6];
void build(int idx,int L,int R){
	if(L==R){
		tr[idx].x=l[L];
		return;
	}
	int mid=(L+R)/2;
	build(L(idx),L,mid);
	build(R(idx),mid+1,R);
	tr[idx].x=min(tr[L(idx)].x,tr[R(idx)].x);
}
int que(int idx,int ll,int rr,int L,int R){
	int mid=(L+R)/2;
	if(ll==L && rr==R){
        return tr[idx].x;
	}
	if(rr<=mid){
		return que(L(idx),ll,rr,L,mid);
	}else if(ll>=mid+1){
		return que(R(idx),ll,rr,mid+1,R);
	}else{
		return min(que(L(idx),ll,mid,L,mid),que(R(idx),mid+1,rr,mid+1,R));
	}
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("G:/in.txt","r",stdin);
	//freopen("G:/myout.txt","w",stdout);
#endif
	cin>>(str+1);
	//cin>>tmp;
	int n;cin>>n;
	int len=strlen(str+1);
	for(int i=1;i<=len;i++){
		l[i]=l[i-1];
		r[i]=r[i-1];
		if(str[i]=='('){
			l[i]++;
		}else{
			if(l[i]){
				l[i]--;
				r[i]++;
			}
		}
	}
	build(1,1,len);
	while(n--){
		int x,y;cin>>x>>y;
		if(x==y){
            cout<<0<<endl;
            continue;
		}
		int ans=r[y]-r[x-1];
		ans-=max(0,l[x-1]-que(1,x,y,1,len));
		cout<<ans*2<<endl;
	}
}


CF380C Sereja and Brackets [想法+线段树]