囧仙 的博客

囧仙 的博客

题解 CF1263E 【Editor】

posted on 2020-10-04 11:14:10 | under 题解 |

题目大意

$n$ 次操作,每次修改一个字符。询问每次操作后嵌套层数最多的括号有多少层。如果这个括号序列不合法,输出 $-1$ 。

题解

括号问题,一般需要给括号加上权值,然后统计前缀和。我们不妨将左括号赋值为 $1$ ,右括号赋值为 $-1$ 。显然,如果这个括号序列合法,必定满足:

  • 所有括号的权值和为 $0$ 。(即左右括号数量相等)。

  • 不存在一个位置,它的前缀和是负数。(否则某个位置左侧的右括号多余左括号,显然不合法)。

若括号序列合法,那么括号嵌套的最多次数就是前缀和的最大值。

这点比较显然。设某个点的前缀和为 $x$ ,那么就说明它左侧的左括号比右括号多 $x$ 个,也即这个点在第 $x$ 层里。

想到这里,就可以直接用线段树维护前缀和最大值、前缀和最小值了。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;++i)
#define dn(r,l,i) for(int i=r;i>=l;--i)
using namespace std ;
int qread(){
    int w=1,c,r=0;
    for(c=getchar();!isdigit(c);c=getchar())
    if(c=='-') w=-1; else w=1; r=c-'0';
    for(c=getchar(); isdigit(c);c=getchar())
    r=r*10+c-'0';
    return r*w;
}
const int MAXN =1e6+3,MAXM=1e6+3,SIZ=4e6+3;
#define lc(o) (o<<1)
#define rc(o) (o<<1|1)
int M[SIZ],N[SIZ],T[SIZ],n;
void upd(int o,int a,int b){
    if(!T[o]) return; int d=T[o];
    M[lc(o)]+=d,M[rc(o)]+=d,T[lc(o)]+=d;
    N[lc(o)]+=d,N[rc(o)]+=d,T[rc(o)]+=d;
    T[o]=0;
}
void cng(int o,int l,int r,int k,int a,int b){
    int c=(a+b)>>1;
    if(l<=a&&b<=r){
        M[o]+=k,N[o]+=k,T[o]+=k;
        return ;
    }
    upd(o,a,b);
    if(l<=c) cng(lc(o),l,r,k,a,c);
    if(r> c) cng(rc(o),l,r,k,c+1,b);
    M[o]=max(M[lc(o)],M[rc(o)]);
    N[o]=min(N[lc(o)],N[rc(o)]);
}
void get(int o,int l,int r,int a,int b,int &p,int &q){
    int c=(a+b)>>1;
    if(l<=a&&b<=r){
        p=max(p,M[o]),q=min(q,N[o]);
        return ;
    }
    upd(o,a,b);
    if(l<=c) get(lc(o),l,r,a,c,p,q);
    if(r> c) get(rc(o),l,r,c+1,b,p,q);
}
int w=1,A[MAXN],s;
int main(){
    n=qread(); up(1,n,i){
        int op=getchar();
        if(op=='L') --w; else if(op=='R') ++w; else{
            if(A[w]=='(') cng(1,w,n,-1,1,n),--s; else
            if(A[w]==')') cng(1,w,n, 1,1,n),++s;
            if(op=='(') cng(1,w,n, 1,1,n),++s; else
            if(op==')') cng(1,w,n,-1,1,n),--s;
            A[w]=op;
        }
        if(w<1) ++w;
        int a=-1e9,b=1e9,t; get(1,1,n,1,n,a,b);
        if(s!=0||b<0) printf("%d ",-1); else printf("%d ",a);
    }
    return 0;
}