Codeforces Round #529 (Div. 3)
题意：
给你由左右括号组成的字符串，问你有多少处括号翻转过来是合法的序列
思路：
这么考虑：
如果是左括号
1）整个序列左括号个数比右括号多 2
2）在这个位置之前，所有位置的前缀左括号个数都不少于前缀右括号个数
3）在这个位置和这个位置之后，在修改后所有位置的前缀左括号个数减去前缀右括号个数大于2
（这里这么想，把左变成右，左-1，右+1）
右括号也是这样
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+;
int a[N],pre[N],post[N];
char s[N];
int n;
int main()
{
while(~scanf("%d",&n))
{
scanf("%s",s+);
int x=;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
if(s[i]=='(') x++;
else x--;
a[i]=x;
}
pre[]=N,post[n]=N;
for(int i=;i<n;i++) pre[i]=min(pre[i-],a[i]);
for(int i=n-;i>=;i--) post[i]=min(post[i+],a[i]);
int ans=;
if(x!=-&&x!=)
{
printf("0\n");
}
else{
for(int i=;i<=n;i++)
{
if(s[i]=='(')
{
if(pre[i-]>=&&post[i]>=&&x==) ans++;
}
else if(pre[i-]>=&&post[i]>=-&&x==-) ans++;
}
printf("%d\n",ans);
}
}
}