CF1095E Almost Regular Bracket Sequence

题目地址：CF1095E Almost Regular Bracket Sequence

真的是尬，Div.3都没AK，难受QWQ

就死在这道水题上（水题都切不了，我太菜了）

看了题解，发现题解有错，不过还是看懂了QAQ

其实是一道好题 （话说CF的题有不好的么（雾

难在预处理

预处理两个数组：

前缀和：若 \(s_i\) 为 \((\) ， \(s1_i=s1_{i-1}+1\) ，反之同理；

后缀和：若 \(s_i\) 为 \()\) ， \(s2_i=s2_{i+1}+1\) ，反之亦同理。

再预处理两个bool数组：

从头到尾扫，若 \(s1_i>=0\) ， \(v1_i=true\) ，否则立刻跳出循环；

从尾到头扫，若 \(s2_i>=0\) ， \(v2_i=true\) ，否则亦立刻跳出循环；

！！！注意， \(v1_0=v2_{n+1}=true\) ！！！

最后逐个判断每个位置能否被替换即可（如何判断请自行根据代码脑补）

#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, s1[N], s2[N];
bool v1[N], v2[N];
char s[N];

int main() {
    cin >> n;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
        s1[i] = s1[i-1] + (s[i] == '(' ? 1 : -1);
    for (int i = 0; i <= n; i++)
        if (s1[i] >= 0) v1[i] = 1;
        else break;
    for (int i = n; i; i--)
        s2[i] = s2[i+1] + (s[i] == ')' ? 1 : -1);
    for (int i = n + 1; i; i--)
        if (s2[i] >= 0) v2[i] = 1;
        else break;
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (v1[i-1] && v2[i+1]) {
            if (s[i] == '(') {
                if (s1[i-1] > 0 && s1[i-1] - 1 == s2[i+1]) ans++;
            } else {
                if (s1[i-1] + 1 == s2[i+1]) ans++;
            }
        }
    cout << ans << endl;
    return 0;
}

CF1095E Almost Regular Bracket Sequence的相关教程结束。