codeforces div2 603 E. Editor(线段树)

题目链接：https://codeforces.com/contest/1263/problem/E

题意：一个编译器，每次输入一些字符，R表示光标右移，L表示光标左移，然后有一些左括号（和右括号），每次会询问当前输入的数据的括号是否合法，如果不合法输出-1，如果合法输出最大合法的括号对数，合法的括号就是（）这种形式的。

思路：大致思路是用线段树维护区间一个区间前缀和，初始化前缀和为0。遇到单点更新，（让管辖区间+1，）就让管辖区间-1，，判断是否是合法括号需要判断区间最小值是否为0，且保证1到n区间的前缀和为0（画图思考一下），满足两种条件的同时才能说明此为合法括号序列，最终查询区间最大值就是最大匹配的括号对数（画图思考）。

代码：

  1 #include<iostream>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<queue>
  7 #include<cstring>
  8 #include<set>
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 typedef long long LL;
 12 const int maxn = 1e6+10;
 13 struct node{
 14     int l,r;
 15     int Min,Max;
 16     int val;
 17     int lazy; 
 18 }tree[maxn*4+5];
 19 void pushdown(int index){
 20     if(tree[index].lazy){
 21         tree[index<<1].val += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].lazy;
 22         tree[index<<1|1].val +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].lazy;
 23         tree[index<<1].Max += tree[index].lazy;
 24         tree[index<<1|1].Max += tree[index].lazy;
 25         tree[index<<1].Min += tree[index].lazy;
 26         tree[index<<1|1].Min += tree[index].lazy;
 27         tree[index<<1].lazy += tree[index].lazy;
 28         tree[index<<1|1].lazy += tree[index].lazy;
 29         tree[index].lazy = 0;
 30     }
 31 }
 32 void pushup(int index){
 33     tree[index].val = tree[index<<1].val+tree[index<<1|1].val;
 34     tree[index].Max = max(tree[index<<1].Max,tree[index<<1|1].Max);
 35     tree[index].Min = min(tree[index<<1].Min,tree[index<<1|1].Min);
 36 }
 37 
 38 void build(int l,int r,int index){//建树  
 39     tree[index].l = l,tree[index].r = r,tree[index].lazy = 0;
 40     if(l == r){
 41         //scanf("%d",&tree[index].val);
 42         tree[index].val = 0;
 43         tree[index].Max = tree[index].Min = tree[index].val;
 44         return;
 45     }
 46     int mid = (l+r)>>1;//
 47     build(l,mid,index<<1);
 48     build(mid+1,r,index<<1|1);
 49     pushup(index);
 50 } 
 51 void update(int l,int r,int index,int val){//区间修改 
 52     if(l <= tree[index].l && r >= tree[index].r){
 53         tree[index].val += (tree[index].r-tree[index].l+1)*val;
 54         tree[index].Max += val;
 55         tree[index].Min += val;
 56         tree[index].lazy += val;//延时标记
 57         return ;
 58     }
 59     pushdown(index);
 60     int mid = (tree[index].l+tree[index].r)>>1;
 61     if(l <= mid){
 62         update(l,r,index<<1,val);
 63     }
 64     if(r > mid){
 65         update(l,r,index<<1|1,val);
 66     }
 67     pushup(index);
 68 }
 69 
 70 LL query_range(int l,int r,int index){//区间查询 
 71     if(l <= tree[index].l && r >= tree[index].r){
 72         return tree[index].val;
 73         //return tree[index].mn;
 74     }
 75     pushdown(index);
 76     int mid = (tree[index].l+tree[index].r)>>1;
 77     LL res = 0;
 78     LL Max = 0;
 79     LL Min = inf;
 80     if(l <= mid){
 81         res += query_range(l,r,index<<1);
 82     }
 83     if(r > mid){
 84         res += query_range(l,r,index<<1|1);
 85     }
 86     return res;
 87 }
 88 
 89 LL query_max(int l,int r,int index){//最大值查询 
 90     if(l<= tree[index].l && r>= tree[index].r ){
 91         return tree[index].Max;
 92     }
 93     pushdown(index);
 94     int mid = (tree[index].l + tree[index].r )>>1;
 95     LL ans = 0;
 96     LL MAX = 0,MIN = inf;
 97     if(l <= mid) MAX = max(query_max(l,r,index<<1),MAX);
 98     if(r > mid) MAX = max(query_max(l,r,index<<1|1),MAX);
 99     return MAX;
100 }
101 LL query_min(int l,int r,int index){//最小值查询 
102     if(l<= tree[index].l && r>= tree[index].r ){
103         return tree[index].Min;
104     }
105     pushdown(index);
106     int mid = (tree[index].l + tree[index].r )>>1;
107     LL ans = 0;
108     LL MAX = 0,MIN = inf;
109     if(l <= mid) MIN = min(query_min(l,r,index<<1),MIN);
110     if(r > mid) MIN = min(query_min(l,r,index<<1|1),MIN);
111     return MIN;
112 }
113 string s;
114 LL ss[maxn];
115 int main(){
116     int n;
117     scanf("%d",&n);
118     n = n+10;
119     build(1,n,1);
120     cin>>s;
121     int pos = 1;
122     vector<int> ans;
123     for(int i = 0;i<s.length() ;i++){
124         if(s[i] == '('){
125             update(pos,n,1,1-ss[pos]);
126             ss[pos] = 1;
127         }
128         else if(s[i] == ')'){
129             update(pos,n,1,-1-ss[pos]);
130             ss[pos] = -1;
131         }
132         else if(s[i] == 'R'){
133             pos++;
134         }
135         else if(s[i] == 'L'){
136             if(pos>1) pos--;
137         } 
138         else{
139             if(ss[pos] == 1){
140                 update(pos,n,1,-1);
141             }
142             else if(ss[pos] == -1){
143                 update(pos,n,1,1);
144             }
145             ss[pos] = 0;
146         }
147         if(query_min(1,n,1) == 0 && query_range(n,n,1) == 0){
148             ans.push_back(query_max(1,n,1)); 
149         }
150         else{
151             ans.push_back(-1); 
152         }
153     }
154     for(int i = 0;i<ans.size() ;i++){
155         cout<<ans[i]<<" ";
156     }
157     //cout<<endl;
158     return 0;
159 }