E. Editor
题目链接：
https://codeforces.com/contest/1263/problem/E
题目大意：
输入一个字符串S1含有‘（’ ， ‘）’ ， ‘R’ ， ‘L’ 以及其他字符。根据这个字符串，得到相应的字符串S2。起始idx=1即S2的初始坐标，然后从左到右读取S1，当遇到'L'，idx减小1（当无法左移的情况下idx不减小），当遇到'R'，idx增加1，当读取到其他字符时，将idx这个位置上的字符更新为读取到的新的字符。然后输出每一步得到的字符串S2最大的括号级数（例：（（）（））为2，（（（）））为3），如果不是一个左右括号完全匹配的字符串输出-1。
解题思路：
另（为1，）为-1，其他字符为0，构造一个线段树，维护区间和与前缀最小值、前缀最大值。可以知道，当前缀最小值小于0时代表不是一个括号完全匹配的字符串，当区间和不为0也表示这不是一个括号完全匹配的字符串。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6;
string s;
int ans[N];
int mi[N],ma[N]; void update(int node,int start,int end,int p,int v){
if(start==end){
ans[node]=v;
ma[node]=v;
mi[node]=v;
return ;
}
int mid=(start+end)>>;
int left_node=*node+;
int right_node=*node+;
if(p<=mid){
update(left_node,start,mid,p,v);
}
else{
update(right_node,mid+,end,p,v);
}
ans[node]=ans[left_node]+ans[right_node];
ma[node]=max(ma[left_node],ans[left_node]+ma[right_node]);// 一个区间前缀最大值是左边区间中的最大值，与右边区间最大值加上左边区间和中的最大值
mi[node]=min(mi[left_node],ans[left_node]+mi[right_node]);// 一个区间前缀最小值是左边区间中的最小值，与右边区间最小值加上左边区间和中的最小值
} int main(){
int n,idx=;
cin>>n>>s;
for(int i=;i<n;i++){
if(s[i]=='L'){
if(idx>) idx--;
}
else if(s[i]=='R'){
idx++;
}
else if(s[i]=='('){
update(,,n,idx,);//更新此位置改为1
}
else if(s[i]==')'){
update(,,n,idx,-);//更新此位置改为-1
}
else{
update(,,n,idx,);//更新此位置改为0
}
if(mi[]>=&&ans[]==){//判断输出
cout<<ma[]<<" ";
}
else{
printf("-1 ");
}
}
cout<<endl; return ;
}