题解 CF1263E 【Editor】

## 题目大意 $n$ 次操作，每次修改一个字符。询问每次操作后嵌套层数最多的括号有多少层。如果这个括号序列不合法，输出 $-1$ 。 ## 题解 括号问题，一般需要给括号加上权值，然后统计前缀和。我们不妨将左括号赋值为 $1$ ，右括号赋值为 $-1$ 。显然，如果这个括号序列合法，必定满足： - 所有括号的权值和为 $0$ 。（即左右括号数量相等）。 - **不存在一个位置，它的前缀和是负数**。（否则某个位置左侧的右括号多余左括号，显然不合法）。 若括号序列合法，那么括号嵌套的最多次数就是前缀和的最大值。 这点比较显然。设某个点的前缀和为 $x$ ，那么就说明它左侧的左括号比右括号多 $x$ 个，也即这个点在第 $x$ 层里。 想到这里，就可以直接用线段树维护前缀和最大值、前缀和最小值了。 ## 参考代码 ```cpp #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; } ```