tag 说是思维题，其实也是合法括号串类问题的通用 trick。

我们将 ( 当做 $+1$ ，) 当做 $-1$ ，那么如果一个串是合法括号序列，那么这一段的区间和必须是 $0$ ，且这个区间的前缀和在任何时刻都不小于 $0$ 。

基于此，我们可以记录整个序列的前缀和，以及前缀和的前缀和后缀 $\min$ 。修改位置 $p$ 时，如果是 ( 改成 ) 就是 $p$ 以及之后的前缀和整体都减去 $2$，可以直接用后缀 $\min$ 减去 $2$ 来表示。从 ) 改成 ( 类似处理，就是加 $2$ 。于是每一位我们去判断修改完之后，前缀 $\min$ 和后缀 $\min$ 是否大于等于 $0$ 即可。最后再判断修改完之后整个序列的区间和是否等于 $0$ 。时间复杂度线性。

#include <stdio.h>
#define min(a, b) (((a) < (b)) ? (a) : (b))
int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9') k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
int rd_op()
{
    char c = getchar();
    while (c != '(' && c != ')') c = getchar();
    return (c == '(') ? 1 : -1;
}
#define N 1000010
int n, ans;
int a[N];
int s[N], pre_mn[N], suf_mn[N];
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd_op(), s[i] = s[i - 1] + a[i];
    pre_mn[1] = s[1], suf_mn[n] = s[n];
    for (int i = 2; i <= n; ++i) pre_mn[i] = min(pre_mn[i - 1], s[i]);
    for (int i = n - 1; i; --i) suf_mn[i] = min(suf_mn[i + 1], s[i]);

    for (int i = 1; i <= n; ++i)
    {
        int delta = (a[i] > 0) ? -2 : 2;
        ans += (s[n] + delta == 0) && (pre_mn[i - 1] >= 0) && (suf_mn[i] + delta >= 0);
    }
    printf("%d", ans);
}