uestc 1546 Bracket Sequence(セグメントツリーかっこマッチング)

Bracket Sequence

Time Limit: 3000 ms Memory Limit: 65536 kB Solved: 28 Tried: 380

Description

There is a sequence of brackets, which supports two kinds of operations. 1. we can choose a interval [l,r], and set all the elements range in this interval to left bracket or right bracket.  2. 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 opearations. Let us define a regular brackets sequence in the following way:  1. Empty sequence is a regular sequence.  2. If S is a regular sequence, then (S) is also a regular sequences.  3. If A and B are regular sequences, then AB is a regular sequence.

Input

In the first line there is an integer T (T≤10), indicates the number of test cases. Each case begins with a line containing an integers N (N ≤ 100,000 and N is a even number), the size of the initial brackets sequence. The next line contains a string whose length is N consisting of '(' and ')'. In the third of each test case, there is an integer M(M ≤ 100,000) indicates the number of queries. Each of the following M lines contains one operation as mentioned below. The index of the bracket sequence is labeled from 0 to N - 1. Three operation description: set l r c: change all the elements range in [l,r] into '(' or ')'.(c is '(' or ')') reverse l r: reverse the interval [l,r] query l,r: you should answer that interval [l,r] is regular or not

Output

For each test case, print a line containing the test case number (beginning with 1) on its own line, then the answer for each "query"operation, if the interval is regular, print "YES", otherwise print "NO", one on each line. Print a blank line after each test case.

Simple Input

1 6 ((())) 8 query 0 5 set 0 5 ( query 0 5 reverse 3 5 query 0 5 query 1 4 query 2 3 query 0 4

Simple Output

Case 1: YES NO YES YES YES NO

Hint

Huge input, use "scanf"instead of "cin".

Source

Classic Problem


タイトル:http://acm.uestc.edu.cn/problem.php?pid=1546
标题:左右の括弧を1列あげて、毎回1つの区間の括弧を選んで、あるいはすべて左の括弧になって、あるいは右の括弧になって、あるいは逆を取って、つまり左の括弧は右の括弧になります...この区間の括弧がちょうど完全に一致しているかどうかを尋ねる質問かもしれません..
分析:この問題は最初は何も考えていなかったが、主に永遠に一致しない可能性があると思っていたが、実はそれは多種のかっこだった.その後、一致した残りの左かっこを保存し、一致した残りの右かっこを保存した.区間の左か右か気にする必要はありません.つまり、区間の残りが一致していない括弧の場合、0が残っていれば完全に一致しますが、区間はどのように更新されますか.残りの'('=左サブツリー'('-min{左サブツリー'(',右サブツリー')}+右サブツリー'(';残りの')'=右サブツリー')'-min{左サブツリー'(',右サブツリー')}+右サブツリー')';これで区間全体の状況を算出できますが、逆を取る場合は左かっこを右かっことして集計し、逆を取る必要がある場合は2つの統計を逆にすればいいのですが、1つの区間のsetやrevについては、先に操作してからマークし、setであれば必ずrevマークをクリアしなければなりません(これはうっかりしていませんが、waは1日でした...)
以上は私の最初の考えで、もちろん、このようにするのは絶対に正解で、誰かがこのようにしたのを見たからです==
后で私は上の书き方が面倒かもしれないと思って、それから他の人の1种の书き方を使って、左かっこを-1として、右かっこを1として、1つの区间に対して、左から右の和の最大値が0で、しかも区间の和が0であれば、この区间は完全に一致して、これは证明しません.更新時の区間の和はもちろんですが、区間は左から右の最値で、これは2つから最値=max(左サブツリー最値、左サブツリーと+右サブツリー最値)を取らなければなりません.
逆にすると区間と直接逆の数をとり、最値にすると毎回最大と最小値を保存し、次に最大値=最小値の逆の数をとり、最小値は同じ...遅延フラグの注意点は同じです...
最后にこの书き方が书きにくいようで、実现の复雑さは少し高いようで、私が挫折したのかもしれません==、第1种は书かないで、涙が走ります~~~
コード:

#include<cstdio>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int mm=111111;
int dly[mm<<2],rev[mm<<2],sum[mm<<2],lmax[mm<<2],lmin[mm<<2];
char str[mm];
void reverse(int rt)
{
    sum[rt]=-sum[rt];
    int tmp=lmax[rt];
    lmax[rt]=-lmin[rt];
    lmin[rt]=-tmp;
    rev[rt]^=1;
}
void set(int rt,int op,int len)
{
    sum[rt]=op*len;
    lmax[rt]=sum[rt]>0?sum[rt]:0;
    lmin[rt]=sum[rt]<0?sum[rt]:0;
    dly[rt]=op,rev[rt]=0;
}
int pushdown(int rt,int l1,int l2)
{
    if(rev[rt])
    {
        if(dly[rt])dly[rt]=-dly[rt];
        else reverse(rt<<1),reverse(rt<<1|1);
        rev[rt]=0;
    }
    if(dly[rt])
    {
        set(rt<<1,dly[rt],l1),set(rt<<1|1,dly[rt],l2);
        dly[rt]=0;
    }
}
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
    lmin[rt]=min(lmin[rt<<1],sum[rt<<1]+lmin[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    dly[rt]=rev[rt]=0;
    if(l==r)
    {
        sum[rt]=(str[l]=='(')?-1:1;
        lmax[rt]=(sum[rt]<0)?0:1;
        lmin[rt]=(sum[rt]<0)?-1:0;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void updata(int L,int R,int op,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        if(op)set(rt,op,r-l+1);
        else reverse(rt);
        return;
    }
    int m=(l+r)>>1;
    pushdown(rt,m-l+1,r-m);
    if(L<=m)updata(L,R,op,lson);
    if(R>m)updata(L,R,op,rson);
    pushup(rt);
}
int querys(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)return sum[rt];
    int m=(l+r)>>1,ret=0;
    pushdown(rt,m-l+1,r-m);
    if(L<=m)ret+=querys(L,R,lson);
    if(R>m)ret+=querys(L,R,rson);
    pushup(rt);
    return ret;
}
int querym(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)return lmax[rt];
    int m=(l+r)>>1,ret;
    pushdown(rt,m-l+1,r-m);
    if(R<=m)ret=querym(L,R,lson);
    else if(L>m)ret=querym(L,R,rson);
    else ret=max(querym(L,R,lson),querys(L,R,lson)+querym(L,R,rson));
    pushup(rt);
    return ret;
}
int main()
{
    int i,j,n,m,t,cs;
    char op[55];
    scanf("%d",&t);
    for(cs=1;cs<=t;++cs)
    {
        printf("Case %d:
",cs);
        scanf("%d%s%d",&n,str,&m);
        build(0,n-1,1);
        while(m--)
        {
            scanf("%s%d%d",op,&i,&j);
            if(op[0]=='s')
            {
                scanf("%s",op);
                updata(i,j,op[0]=='('?-1:1,0,n-1,1);
            }
            else if(op[0]=='r')updata(i,j,0,0,n-1,1);
            else if(!querys(i,j,0,n-1,1)&&!querym(i,j,0,n-1,1))puts("YES");
            else puts("NO");
        }
        puts("");
    }
    return 0;
}