[CF Round #603]E.Editor

CaprYang属实nb。

Editor

题目大意:给你一个长度为$n$的字符串,只包含 ‘R’ , ‘L’ , ‘(‘ , ‘)’ 以及小写字母,如果当前字母为‘R’或’L’,就右移或左移(左移最多为位置0),其他字符均为替换,问如果当前的字符串为合法字符串(所有的括号均可匹配即为合法),问当前括号最多套了多少层,如果不合法,输出”-1“。

线段树查询区间最大最小值。对于每个操作,如果修改的为括号,则修改线段树。

对于每个’(‘,我们从当前位置直到最后位置均+1;对于每个’)’,我们从当前位置直到最后位置均-1,同时记录左括号和右括号数量的差。对于一个合法序列,它的左括号数量等于右括号数量;再根据我们上面的操作能够看出,若合法,那么每个位置的值都不会小于0,若是合法,那么从起始位置到任意位置区间内,左括号数量大于等于右括号数量,不会出现小于0的情况。因此我们判断以上两个条件即可。若是合法,区间最大值即为当前括号最多层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
const int maxn=3000000+10;
const int INF=0x3f3f3f3f;
int maxx[maxn],minn[maxn],lzy[maxn];
int n,N;
char s[maxn],t[maxn];
void build(int x){
N=1;
while(N<=x) N*=2;
}
void pushdown(int k){
maxx[k*2+1]+=lzy[k];
maxx[k*2+2]+=lzy[k];
minn[k*2+1]+=lzy[k];
minn[k*2+2]+=lzy[k];
lzy[k*2+1]+=lzy[k];
lzy[k*2+2]+=lzy[k];
lzy[k]=0;
}
void update(int a,int b,int l,int r,int k,int x){
if(b<l || r<a) return ;
if(a<=l && r<=b){
maxx[k]+=x;
minn[k]+=x;
lzy[k]+=x;
}
else{
pushdown(k);
update(a,b,l,(l+r)/2,k*2+1,x);
update(a,b,(l+r)/2+1,r,k*2+2,x);
maxx[k]=max(maxx[k*2+1],maxx[k*2+2]);
minn[k]=min(minn[k*2+1],minn[k*2+2]);
}
}
int main()
{
int n;
scanf("%d",&n);
build(n);
scanf("%s",s);
int pos=0,sum=0;
for(int i=0;i<n;i++){
int q=0;//记录括号变动情况
if(s[i]=='(') q++;
if(s[i]==')') q--;
if(t[pos]=='(') q--;
if(t[pos]==')') q++;

if(s[i]=='R') pos++;
else if(s[i]=='L') pos=max(pos-1,0);
else{
t[pos]=s[i];
sum+=q;
if(q) update(pos,N-1,0,N-1,0,q);//括号有数量变动
}
if(sum!=0 || minn[0]<0) printf("-1 ");//数量不相等或者从0到某个位置之间右括号数量比左括号多
else printf("%d ",maxx[0]);
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------