Codeforces Round #529 (Div. 3) E. Almost Regular Bracket Sequence

题目大意就是给一个长度为n括号序列，然后问你有几个位置，你将该位置的括号反转之后，这个括号序列可以变成合法的括号序列。合法的括号序列定义就是 1.括号序列里左右括号数量相等 2.对于i位置对应的前缀里左括号数量>=右括号数量（1<=i<=n)

先设左括号为1，右括号为-1，然后求出括号序列对应的前缀和数组a

假设要将pos位置的左括号改成右括号是满足条件的。

那么必有

              1.未修改前左括号个数比右括号个数多2

              2.未修改前 a[i]>=0  (1<=i<=pos-1)，可以等效成min(a[i] (1<=i<=pos-1))>=0

              3.修改之后 a[i]>=0  (pos<=i<=n)

仅仅用这三个条件是无法在题目要求时间内求出答案的，因为第3个条件的判断需要把a[i] （pos<=i<=n)都减2然后再判断是否全都>=0，这样的话时间复杂度很高，所以这里需要优化，因为把pos位置的左括号变成右括号，会对pos位置的前缀值造成-2的作用，当然pos+1到n位置的前缀因为包含了pos位置，所以pos+1到n位置的前缀值也都会-2，总的来说就是a[i]会减小2  （pos<=i<=n)

,然后要求减小后>=0，那么就要a[i]>=2,然后是pos到n范围的前缀值a都满足，那么就等效成min(a[i]  （pos<=i<=n）)>=2.

这样判断pos位置的括号能否反转就仅仅和原数组a有关了，我们只需预处理出前缀数组a的前缀最小值数组premin，和前缀数组a的后缀最小值数组sufmin，就可以对pos位置O(1)判断了，因此总复杂度O(N)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn],premin[maxn],sufmin[maxn];
char s[maxn];
int main()
{
    int n,tmp=0,ans=0,low=0;
    scanf("%d",&n);
    premin[0]=sufmin[n+1]=maxn;
    for(int i=1;i<=n;i++)
    {
        scanf(" %c",&(s[i]));
        if(s[i]=='(')
            tmp+=1;
        else
            tmp-=1;
        a[i]=tmp;
        premin[i]=min(a[i],premin[i-1]);
    }
    for(int i=n;i>=1;i--)
    {
        sufmin[i]=min(a[i],sufmin[i+1]);
    }
    if(n&1||(tmp!=-2&&tmp!=2))
    {
        printf("0
");
        return 0;
    }
    /*
    for(int i=1;i<=n;i++)
        cout<<a[i]<<"   ";
    cout<<endl<<endl;
    for(int i=1;i<=n;i++)
        cout<<premin[i]<<"  ";
    cout<<endl<<endl;
    for(int i=1;i<=n;i++)
        cout<<sufmin[i]<<"  ";
    cout<<endl<<endl;
    */
    if(tmp==2)
        low=2;
    else
        low=-2;
    for(int i=1;i<=n;i++)
    {
        if(tmp==2&&s[i]=='(')
        {
            if(premin[i]>=0&&sufmin[i]>=low)
                ans++;
        }
        else
        {
            if(tmp==-2&&s[i]==')')
            {
                if(i==1&&sufmin[i]>=low)
                    ans++;
                if(i!=1&&premin[i-1]>=0&&sufmin[i]>=low)
                    ans++;
            }
        }
    }
    printf("%d
",ans);
    return 0;
}