Codeforces 1263E Editor（前缀和数组基于线段树的RMQ）

1.在文本中，我们让(值为1，)值为-1，其它值为0，将该文本看成一个int数组，我们就可以得到这个数组的前缀和数组；
2.这个前缀和数组的最大值就是最多嵌套的层数；而最小值如果小于0则说明在从最左侧往右的某一段文本中，有)的数量多于(的情况，这是非法的；
3.同时我们在执行指令的过程中，用一个变量ans来记录第一条里面提到的int数组的总和（其实就是前缀和数组的最后一个有效值），如果ans为0则说明左右括号数相等了；
4.既然查询数组最大/最小值，那就是典型的RMQ问题了，用线段树来做即可；因为涉及到区间修改问题，那引入lazy-tag标记就ok了~；
4.最后如果前缀和数组最小值大于等于0且ans==0，说明左右括号数相等且没有非法格式，输出我们的嵌套层数即可，否则就输出-1；

代码：

#include<bits/stdc++.h>
using namespace std;
inline void out(int x){if(x<0) {putchar('-'); x*=-1;}if(x>9) out(x/10); putchar(x%10+'0');}
const int MAX_N=1e6+5;
int tree[2][MAX_N<<2],tag[MAX_N<<2];  //tree[0]存最大值,tree[1]存最小值 
#define rp(i) for(int i=0;i<2;i++)
void push_down(int rt){
	if(tag[rt]){
		tag[rt<<1]+=tag[rt]; tag[rt<<1|1]+=tag[rt];
		rp(i) tree[i][rt<<1]+=tag[rt],tree[i][rt<<1|1]+=tag[rt];
		tag[rt]=0;
	}
}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void update(int a,int b,int c,int l,int r,int rt){
	if(a<=l&&b>=r){
		rp(i) tree[i][rt]+=c;
		tag[rt]+=c;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(a<=mid) update(a,b,c,lson);
	if(b>mid) update(a,b,c,rson);
	tree[0][rt]=max(tree[0][rt<<1],tree[0][rt<<1|1]);   //往上更新 
	tree[1][rt]=min(tree[1][rt<<1],tree[1][rt<<1|1]); 
}
char c[MAX_N];
int main(){
	int n; string s; int pos=1; int ans=0;
	cin>>n>>s;
	for(int i=0;i<=n;i++) c[i]='a';
	for(int i=0;i<n;i++){
		if(s[i]=='L') {if(pos>1) pos--;}
		else if(s[i]=='R') pos++;
		else if(s[i]=='('){
			if(c[pos]!='('&&c[pos]!=')') update(pos,n,1,1,n,1),ans++;
			else if(c[pos]==')') update(pos,n,2,1,n,1),ans+=2;
			c[pos]='(';
		}else if(s[i]==')'){
			if(c[pos]!='('&&c[pos]!=')') update(pos,n,-1,1,n,1),ans--;
			else if(c[pos]=='(') update(pos,n,-2,1,n,1),ans-=2;
			c[pos]=')';
		}else{
			if(c[pos]=='(') update(pos,n,-1,1,n,1),ans--;
			else if(c[pos]==')') update(pos,n,1,1,n,1),ans++;
			c[pos]='a';
		}
		if(i) putchar(' ');
		if(tree[1][1]<0||ans) out(-1);
		else out(tree[0][1]);
	}
	return 0;
}