(中等) UESTC 94 Bracket Sequence，线段树+括号。

　　There is a sequence of brackets, which supports two kinds of operations.

we can choose a interval [l,r], and set all the elements range in this interval to left bracket or right bracket.
we can reverse a interval, which means that for all the elements range in [l,r], if it's left bracket at that time, we change it into right bracket, vice versa.

　　Fish is fond of Regular Bracket Sequence, so he want to know whether a interval [l,r] of the sequence is regular or not after doing some operations.

　　Let us define a regular brackets sequence in the following way:

Empty sequence is a regular sequence.
If S is a regular sequence, then (S) is also a regular sequences.
If A and B are regular sequences, then AB is a regular sequence.

　　

　　题目大意就是说给你一个括号序列，对他进行操作和询问，包括反转和覆盖两个操作。

　　维护一个总和，还有一个最小前缀和（还要维护最大前缀和，在反转的时候计算最小的。）。当总和和最小前缀和都为0，则成立。

　　这个题又被坑了好久，没办法，水平太差了，错了十几次，电子科大的提交记录都被我刷屏了。。。错误百出。。。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#define lson L,M,po*2

#define rson M+1,R,po*2+1

#define max(a,b) (a>b?a:b)

#define min(a,b) (a<b?a:b)

using namespace std;

int BIT[*];

int QS[*];

int MS[*];

int XOR[*];

int COL[*];

char ss[];

void pushUP(int po)

{

    BIT[po]=BIT[po*]+BIT[po*+];

    QS[po]=max(QS[po*],BIT[po*]+QS[po*+]);            //这里要注意。

    MS[po]=min(MS[po*],BIT[po*]+MS[po*+]);

}

void pushDown(int po,int len)

{

    if(COL[po])

    {

        COL[po*]=COL[po];

        COL[po*+]=COL[po];

        XOR[po*]=XOR[po*+]=;                //这里不能忘记。

        BIT[po*]=(len-(len/))*COL[po];

        BIT[po*+]=(len/)*COL[po];

        QS[po*]=max(-,BIT[po*]);

        QS[po*+]=max(-,BIT[po*+]);

        MS[po*]=min(,BIT[po*]);

        MS[po*+]=min(,BIT[po*+]);

        COL[po]=;

    }

    if(XOR[po])

    {

        int temp;

        XOR[po*]=!XOR[po*];

        XOR[po*+]=!XOR[po*+];

        BIT[po*]=-BIT[po*];

        BIT[po*+]=-BIT[po*+];

        temp=QS[po*];

        QS[po*]=-MS[po*];

        MS[po*]=-temp;

        temp=QS[po*+];

        QS[po*+]=-MS[po*+];

        MS[po*+]=-temp;

        XOR[po]=;

    }

}

void build_tree(int L,int R,int po)

{

    XOR[po]=;

    COL[po]=;

    if(L==R)

    {

        if(ss[L]=='(')

        {

            BIT[po]=;

            QS[po]=;

            MS[po]=;

        }

        else

        {

             BIT[po]=-;

            QS[po]=-;

            MS[po]=-;

        }

        return;

    }

    int M=(L+R)/;

    build_tree(lson);

    build_tree(rson);

    pushUP(po);

}

void update_col(int ul,int ur,int ut,int L,int R,int po)

{

    if(ul<=L&&ur>=R)

    {

        XOR[po]=;

        COL[po]=ut;

        BIT[po]=ut*(R-L+);

        QS[po]=max(-,BIT[po]);

        MS[po]=min(,BIT[po]);

        return;

    }

    pushDown(po,R-L+);

    int M=(L+R)/;

    if(ul<=M)

        update_col(ul,ur,ut,lson);

    if(ur>M)

        update_col(ul,ur,ut,rson);

    pushUP(po);

}

void update_xor(int ul,int ur,int L,int R,int po)

{

    if(ul<=L&&ur>=R)

    {

        XOR[po]=!XOR[po];

        BIT[po]=-BIT[po];

        int temp=QS[po];

        QS[po]=-MS[po];

        MS[po]=-temp;

        return;

    }

    pushDown(po,R-L+);

    int M=(L+R)/;

    if(ul<=M)

        update_xor(ul,ur,lson);

    if(ur>M)

        update_xor(ul,ur,rson);

    pushUP(po);

}

int query(int &qs,int ql,int qr,int L,int R,int po)            //不能忘记写 ＆ ！！！

{

    if(ql<=L&&qr>=R)

    {

        qs=MS[po];

        return BIT[po];

    }

    pushDown(po,R-L+);

    int M=(L+R)/;

    int ans=;

    if(qr<=M)

        return query(qs,ql,qr,lson);

    if(ql>M)

        return query(qs,ql,qr,rson);

    int temp1,temp2,a1;

    a1=query(temp1,ql,qr,lson);

    ans=a1+query(temp2,ql,qr,rson);

    qs=min(temp1,temp2+a1);

    return ans;

}

bool getans(int ql,int qr,int N)

{

    int t1;

    int ans;

    if((qr-ql)%==)

        return ;

    ans=query(t1,ql,qr,,N,);

    if(ans==&&t1==)

        return ;

    else

        return ;

}

int main()

{

    int T;

    int N,Q;

    char t1[],t2[];

    int a,b;

    cin>>T;

    for(int cas=;cas<=T;++cas)

    {

        printf("Case %d:\n",cas);

        scanf("%d",&N);

        scanf("%s",ss);

        build_tree(,N-,);                    //这里应该是N-1。

        scanf("%d",&Q);

        for(int i=;i<Q;++i)

        {

            scanf("%s %d %d",t1,&a,&b);

            if(t1[]=='s')

            {

                scanf("%s",t2);

                update_col(a,b,t2[]=='('?:-,,N-,);

            }

            else if(t1[]=='r')

                update_xor(a,b,,N-,);

            else

                if(getans(a,b,N-))

                    printf("YES\n");

                else

                    printf("NO\n");

        }

        printf("\n");

    }

    return ;

}

(中等) UESTC 94 Bracket Sequence，线段树+括号。的相关教程结束。