CF1095E Almost Regular Bracket Sequence

给定一个长度为 \(n\) 的小括号序列，求有多少个位置满足将这个位置的括号方向反过来后使得新序列是一个合法的括号序列。

这道题要用到高级前缀和+后缀和。

我们设两个int数组\(s1\)和\(s2\)，两个bool数组\(b1\)和\(b2\)。

\(s1\)数组这么处理：顺序遍历字符串，遇到左括号\(+1\)，遇到右括号\(-1\)。

\(s2\)数组这么处理：逆序遍历字符串，遇到右括号\(+1\)，遇到左括号\(-1\)。

\(b1\)数组这么处理：\(s1\)数组相应值\(\geq 0\)的下标为true。

\(b2\)数组这么处理：\(s2\)数组相应值\(\geq 0\)的下标为true。

显然，\(b1\)和\(b2\)数组为true的地方，前面才不会产生别的不匹配，才能考虑与答案计算。

最后，遍历字符串，设找到第\(i\)个时，当前后都合法时，分两种情况考虑：

1. 当前字符是左括号。改为右括号后，发现需要满足前面的\(s1\)减\(1\)再减后面的\(s2\)为0，这个点就满足。
2. 当前字符是右括号。改为左括号后，发现需要满足前面的\(s1\)加1再减后面的\(s2\)为0，这个点就满足。

最后输出就完事了。

CF1095E Almost Regular Bracket Sequence

原文：https://www.cnblogs.com/Garen-Wang/p/10349332.html