P9356 「SiR-1」Bracket 做题记录
P9356 「SiR-1」Bracket - 洛谷 (luogu.com.cn)
将 \(\texttt{(}\) 看为 \(1\)，将 \()\) 看为 \(-1\)，整个括号序列看做一个折线图。
首先将末尾补到 \(0\)，若 \(s_n<0\) 则在前边补左括号，\(s_n>0\) 在右边补有括号。
然后考虑进行轮换操作：若进行轮换，选择折线图最低点进行操作可以一步变得合法。
所以只需考虑需不需要进行轮换操作。若 \(s_n>0\)，那么 \(s\) 的最小值 \(\ge 0\) 就不需要轮换；若 \(s_n<0\)，那么 \(s\) 的最小值 \(\ge s_n\) 就不需要轮换。
再考虑区间 \([l,r]\)，不难发现，不需要轮换当且仅当 \(\min_{l-1\le i\le r} s_i\ge \min\{s_{l-1},s_r\}\)。
枚举 \(r\)，维护左边的不降单调栈。若 \(\min_{l-1\le i\le r} s_i=s_r\)，那么 \(l\) 必定合法；否则，需要 \(s_{l-1}=\min_{l-1\le i\le r} s_i\)，即 \(l-1\) 在单调栈里。
需要维护第一个小于栈顶的元素，可以将值相同的元素并起来。复杂度 \(O(n)\)。
int T,n;
char a[N];
int s[N];
int c[N<<1];
pii stk[N]; int top;void Solve(){read(n);scanf("%s",a+1);for(int i=0;i<=n+n;i++) c[i]=0;++c[n];for(int i=1;i<=n;i++){if(a[i]=='(') s[i]=s[i-1]+1;else s[i]=s[i-1]-1;++c[s[i]+n];}ll sum=0,tot=0;ll ans1=0;for(int i=0;i<=n+n;i++){ans1+=c[i]*(tot*i-sum);tot+=c[i],sum+=1ll*i*c[i];}top=0; ll ans2=1ll*n*(n+1)>>1;stk[0]={-1,0};for(int i=0;i<=n;i++){while(top&&s[stk[top].first]>s[i]) --top;if(top&&s[stk[top].first]==s[i]) stk[top].first=i,++stk[top].second;else ++top,stk[top]={i,stk[top-1].second+1};ans2-=i-stk[top-1].first-1+stk[top-1].second;}printf("%lld\n",ans1+ans2);
}signed main(){//静心，long long，数组大小，空间，复杂度，进包，格式 read(T);while(T--) Solve();return 0;
}