Codeforces Round #603 (Div. 2) E. Editor
有一个长度为无限的文本编辑器,初始时光标在位置\(1\)
给定一个长度为\(n\)的字符串作为操作串,该字符串仅含有小写英文字母及\('L'\),\('R'\),\('('\),\(')'\)这四种字符
操作串自左向右每个字符表示文本编辑器的每一次操作
如果字符为\(L\),表示光标向左移动\(1\)格,但如果光标原本就在位置\(1\),则该操作无效
如果字符为\(R\),表示光标向右移动\(1\)格
对于其余所有字符\(c\),表示光标所在位置的字符将会变成\(c\)(覆盖原文本)
其后对于每次操作进行一次询问
如果忽略所有空格和小写字母,只看左右括号,问是否能够达到括号匹配(每个左括号的右边都有与之对应的右括号)
若能,询问括号的最深层次为多少;若不能,输出\(-1\)
\(1\le n\le 10^6\)
对于括号匹配问题,如果我们将左括号\('('\)看作\(1\),将右括号\(')'\)看作\(-1\),其余所有字符看作\(0\)
对于整个字符串做前缀和,得到前缀和数组,能够得到”括号匹配“的充要条件为:
对于光标的移动可以直接进行模拟,对于每次修改,可以使用线段树来维护前缀和数组
例如,如果位置\(p\)此时由空字符变成左括号,表示该位置数值由\(0\)变\(1\),对于前缀和数组而言,\([p,\infty]\)这一段区间内每个位置数值都需要\(+1\)
例如,如果位置\(p\)此时由右括号变成普通小写字母,表示该位置数值由\(-1\)变\(0\),对于前缀和数组而言,\([p,\infty]\)这一段区间内每个位置数值都需要\(+1\)
例如,如果位置\(p\)此时由左括号变成右括号,表示该位置数值由\(1\)变\(-1\),对于前缀和数组而言,\([p,\infty]\)这一段区间内每个位置数值都需要\(-2\)
其余情况进行类似的模拟即可
最后对于每次询问,线段树查找\(\sum[n,n]\)与\(\min[1,n]\)进行上述判断
如果能够得到”括号匹配“,则”最深层次“就是前缀和数组中的最大值,即\(\max[1,n]\)
#include<bits/stdc++.h>
using namespace std;
namespace SegmentTree
{
typedef int SegmentTreeType;
const int MAXN=1e6+50;
const SegmentTreeType SegmentTreeINF=0x3f3f3f3f;
struct SegmentTreeNode
{
int l,r;
SegmentTreeType sum,lazy,maxn,minn;
}tree[MAXN*4];
struct SegmentTreeResult
{
SegmentTreeType sum,minn,maxn;
};
void push_up(int id)
{
tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
tree[id].maxn=max(tree[id<<1].maxn,tree[id<<1|1].maxn);
tree[id].minn=min(tree[id<<1].minn,tree[id<<1|1].minn);
}
void push_down(int id)
{
if(!tree[id].lazy)
return;
int m=tree[id].r-tree[id].l+1;
tree[id<<1].lazy+=tree[id].lazy;
tree[id<<1|1].lazy+=tree[id].lazy;
tree[id<<1].sum+=tree[id].lazy*(m-(m>>1));
tree[id<<1|1].sum+=tree[id].lazy*(m>>1);
tree[id<<1].minn+=tree[id].lazy;
tree[id<<1|1].minn+=tree[id].lazy;
tree[id<<1].maxn+=tree[id].lazy;
tree[id<<1|1].maxn+=tree[id].lazy;
tree[id].lazy=0;
}
void buildTree(int l,int r,int id=1)
{
tree[id].l=l;
tree[id].r=r;
tree[id].lazy=tree[id].sum=tree[id].minn=tree[id].maxn=0;
if(l==r) return;
int mid=(l+r)>>1;
buildTree(l,mid,id<<1);
buildTree(mid+1,r,id<<1|1);
push_up(id);
}
void update(int l,int r,SegmentTreeType val,int id=1)
{
if(l<=tree[id].l&&r>=tree[id].r)
{
tree[id].sum+=val*(tree[id].r-tree[id].l+1);
tree[id].minn+=val;
tree[id].maxn+=val;
tree[id].lazy+=val;
return;
}
push_down(id);
int mid=(tree[id].r+tree[id].l)>>1;
if(l<=mid) update(l,r,val,id<<1);
if(r>mid) update(l,r,val,id<<1|1);
push_up(id);
}
SegmentTreeResult query(int l,int r,int id=1)
{
if(l<=tree[id].l&&r>=tree[id].r)
return {tree[id].sum,tree[id].minn,tree[id].maxn};
push_down(id);
int mid=(tree[id].r+tree[id].l)>>1;
SegmentTreeType sum=0,minn=SegmentTreeINF,maxn=-SegmentTreeINF;
if(l<=mid)
{
SegmentTreeResult res=query(l,r,id<<1);
sum+=res.sum;
minn=min(minn,res.minn);
maxn=max(maxn,res.maxn);
}
if(r>mid)
{
SegmentTreeResult res=query(l,r,id<<1|1);
sum+=res.sum;
minn=min(minn,res.minn);
maxn=max(maxn,res.maxn);
}
return {sum,minn,maxn};
}
SegmentTreeType querySum(int l,int r,int id=1)
{
if(l<=tree[id].l&&r>=tree[id].r)
return tree[id].sum;
push_down(id);
int mid=(tree[id].r+tree[id].l)>>1;
SegmentTreeType ans=0;
if(l<=mid) ans+=querySum(l,r,id<<1);
if(r>mid) ans+=querySum(l,r,id<<1|1);
return ans;
}
SegmentTreeType queryMin(int l,int r,int id=1)
{
if(l<=tree[id].l&&r>=tree[id].r)
return tree[id].minn;
push_down(id);
int mid=(tree[id].r+tree[id].l)>>1;
SegmentTreeType ans=SegmentTreeINF;
if(l<=mid) ans=min(ans,queryMin(l,r,id<<1));
if(r>mid) ans=min(ans,queryMin(l,r,id<<1|1));
return ans;
}
SegmentTreeType queryMax(int l,int r,int id=1)
{
if(l<=tree[id].l&&r>=tree[id].r)
return tree[id].maxn;
push_down(id);
int mid=(tree[id].r+tree[id].l)>>1;
SegmentTreeType ans=-SegmentTreeINF;
if(l<=mid) ans=max(ans,queryMax(l,r,id<<1));
if(r>mid) ans=max(ans,queryMax(l,r,id<<1|1));
return ans;
}
};
using namespace SegmentTree;
int n;
char s[MAXN],t[MAXN];
int main()
{
scanf("%d%s",&n,s);
buildTree(1,n);
int cur=1;
for(int i=0;i<n;i++)
{
if(s[i]=='(')
{
if(t[cur]==')')
update(cur,n,2);
else if(t[cur]!='(')
update(cur,n,1);
t[cur]=s[i];
}
else if(s[i]==')')
{
if(t[cur]=='(')
update(cur,n,-2);
else if(t[cur]!=')')
update(cur,n,-1);
t[cur]=s[i];
}
else if(s[i]=='L')
cur=max(cur-1,1);
else if(s[i]=='R')
cur++;
else
{
if(t[cur]=='(')
update(cur,n,-1);
else if(t[cur]==')')
update(cur,n,1);
t[cur]=s[i];
}
SegmentTreeResult res=query(1,n);
if(querySum(n,n)!=0||res.minn<0)
printf("-1 ");
else
printf("%d ",res.maxn);
}
return 0;
}
联系客服