题解 SP61 【BRCKTS - Brackets】

线段树

容易发现，如果一个括号串的左右括号数相等，且没有任何一个前缀的右括号数量比左括号数量多。
我们分别为左括号和右括号赋值为 1 和 -1 ，并存放在 q 数组里。
考虑对 q 数组做前缀和，记录到 sum 数组里。
这样，判断一个括号串是否是合法的就非常简单了。只要保证对于所有$i$，$sum_i \ge 0$，并且$sum_n=0$即可。
我们可以使用线段树来维护这个前缀和数组。
对于每一次询问，我们用线段树找到全局最小，并判断是否为零。
对于每一次修改，我们直接在线段树区间修改前缀和数组即可。
具体细节可以参照代码，一定注意输出格式。

#include<iostream>
using namespace std;
int sum[30005],q[30005];
struct node{
	int tag,mn;
}a[120005];
inline void up(int rt){
	a[rt].mn=min(a[rt<<1].mn,a[rt<<1|1].mn);
}
inline void pd(int rt){
	if(a[rt].tag){
		a[rt<<1].tag+=a[rt].tag;
		a[rt<<1|1].tag+=a[rt].tag;
		a[rt<<1].mn+=a[rt].tag;
		a[rt<<1|1].mn+=a[rt].tag; 
		a[rt].tag=0;
	}
}
void build(int rt,int l,int r){
	a[rt].tag=0;
	if(l==r){
		a[rt].mn=sum[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	up(rt);
}
void add(int rt,int l,int r,int ql,int qr,int k){
	if(ql<=l&&qr>=r){
		a[rt].tag+=k;
		a[rt].mn+=k;
		return;
	}
	pd(rt);
	int mid=(l+r)>>1;
	if(ql<=mid)add(rt<<1,l,mid,ql,qr,k);
	if(qr>mid)add(rt<<1|1,mid+1,r,ql,qr,k);
	up(rt);
}
//以上为线段树基本操作，区间加和区间最值
int main(){
	for(int _=1;_<=10;_++){//注意，一共10组数据！
		int n,m,total=0,x;//用total记录q数组的和
		char ch;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>ch;
			if(ch=='(')q[i]=1,sum[i]=sum[i-1]+1,total++;
			else q[i]=-1,sum[i]=sum[i-1]-1,total--;
		}//预处理
		build(1,1,n);
		cin>>m;
		cout<<"Test "<<_<<":"<<endl;
		for(int i=0;i<m;i++){
			cin>>x;
			if(x==0){
				if(total==0&&a[1].mn==0)cout<<"YES"<<endl;
				else cout<<"NO"<<endl;
                //mn==0是指判断全局的最小值是否是正数。由于前面对total的判断，一定存在一个位置的值为0。
			}
			else{
				if(q[x]==1)add(1,1,n,x,n,-2),total-=2;
				else add(1,1,n,x,n,2),total+=2;
				q[x]=0-q[x];//翻转括号，调整前缀和数组
			}
		}
	} 
	return 0;
}