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

题意：

给出一串括号

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

分析：

我们能够实现处理两个数组

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

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

这两个数组能够非常easy的扫描一遍动态维护得出来

我们能够先求前缀和，即

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;
	}
}