The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

HDOJ 3397 线段树大综合

实在不行，改了方法。SET 0和SET 1用延迟标记，翻转不用任何标记，直接更新到底。800+MS AC.

#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int const maxn=1000010;
#define Max(a,b) ((a>b?a:b))
#define Min(a,b) ((a<b?a:b))

int LL(int i) {return (i*2);}
int RR(int i){return (i*2+1);}
struct node
{
    int sum;//统计1的个数
    int st;
    int cval0,lval0,rval0;//统计最大连续0,左连续0,右连续0
    int cval1,lval1,rval1;//统计最大连续1,左连续1,右连续1
    int l,r;
    void doit()
    {
        if(st==0)
        {
            cval1=lval1=rval1=0;
            cval0=rval0=lval0=len();
            sum=0;
        }
        else if(st==1)
        {
            cval1=lval1=rval1=len();
            cval0=lval0=rval0=0;
            sum=len();
        }
    }
    int len(){return r-l+1;}
}ST[maxn*8];
int a[maxn];//存输入数据

void reverse(int i)
{
    ST[i].sum=ST[i].len()-ST[i].sum;
    ST[i].st=!ST[i].st;
    swap(ST[i].cval1,ST[i].cval0);
    swap(ST[i].rval1,ST[i].rval0);
    swap(ST[i].lval1,ST[i].lval0);
}

void Up(int i)
{
    if(ST[LL(i)].st!=-1&&ST[RR(i)].st!=-1)
    {
        if(ST[LL(i)].st==ST[RR(i)].st)
            ST[i].st=ST[LL(i)].st;
    }


    ST[i].cval0=Max(ST[LL(i)].cval0,ST[RR(i)].cval0);
    ST[i].cval0=Max(ST[i].cval0,ST[LL(i)].rval0+ST[RR(i)].lval0);
    ST[i].lval0=ST[LL(i)].lval0;
    ST[i].rval0=ST[RR(i)].rval0;
    if(ST[LL(i)].lval0==ST[LL(i)].len())
        ST[i].lval0+=ST[RR(i)].lval0;
    if(ST[RR(i)].rval0==ST[RR(i)].len())
        ST[i].rval0+=ST[LL(i)].rval0;
    //////////////////////////////////////////////////////////////////////////

    ST[i].cval1=Max(ST[LL(i)].cval1,ST[RR(i)].cval1);
    ST[i].cval1=Max(ST[i].cval1,ST[LL(i)].rval1+ST[RR(i)].lval1);
    ST[i].lval1=ST[LL(i)].lval1;
    ST[i].rval1=ST[RR(i)].rval1;
    if(ST[LL(i)].lval1==ST[LL(i)].len())
        ST[i].lval1+=ST[RR(i)].lval1;
    if(ST[RR(i)].rval1==ST[RR(i)].len())
        ST[i].rval1+=ST[LL(i)].rval1;
    //////////////////////////////////////////////////////////////////////////
    ST[i].sum=ST[LL(i)].sum+ST[RR(i)].sum;
    //////////////////////////////////////////////////////////////////////////

}

void Down(int i)
{
    if(ST[i].st!=-1)
    {
        ST[LL(i)].st=ST[RR(i)].st=ST[i].st;
        ST[LL(i)].doit();
        ST[RR(i)].doit();
        ST[i].st=-1;
    }
}


void Build(int l,int r,int i)
{
    ST[i].l=l;
    ST[i].r=r;
    ST[i].st=-1;
    if(l==r)
    {
        ST[i].st=a[l];
        ST[i].sum=a[l];
        if(a[r]==1)
        {
            ST[i].cval1=ST[i].lval1=ST[i].rval1=1;
            ST[i].cval0=ST[i].lval0=ST[i].rval0=0;
        }
        else
        {
            ST[i].cval1=ST[i].lval1=ST[i].rval1=0;
            ST[i].cval0=ST[i].lval0=ST[i].rval0=1;

        }
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,LL(i));
    Build(mid+1,r,RR(i));
    Up(i);

}


void update(int l,int r,int op,int i)
{
    if(l==ST[i].l&&r==ST[i].r)
    {
        ST[i].st=op;
        ST[i].doit();
        return;
    }
    Down(i);
    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)update(l,r,op,LL(i));
    else if(l>mid)update(l,r,op,RR(i));
    else
    {
        update(l,mid,op,LL(i));
        update(mid+1,r,op,RR(i));
    }
    Up(i);
}

void Set_Rev(int l,int r,int i)
{
    if(l==ST[i].l&&r==ST[i].r&&ST[i].st!=-1)
    {
        reverse(i);
        return;
    }
    Down(i);
    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)Set_Rev(l,r,LL(i));
    else if(l>mid)Set_Rev(l,r,RR(i));
    else
    {
        Set_Rev(l,mid,LL(i));
        Set_Rev(mid+1,r,RR(i));
    }
    Up(i);
}

int Query1(int l,int r,int i)//查询[l,r]有多少1
{
    if(ST[i].l==l&&ST[i].r==r)
        return ST[i].sum;
    if(ST[i].st!=-1)
    {
        if(ST[i].st==0)
            return 0;
        else 
            return (r-l+1);
    }
    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)return Query1(l,r,LL(i));
    if(l>mid)return Query1(l,r,RR(i));
    else{return Query1(l,mid,LL(i))+Query1(mid+1,r,RR(i));}
}

int Query2(int l,int r,int i)//查[l,r]中最大连续1
{
    if(ST[i].l==l&&ST[i].r==r)
        return ST[i].cval1;

    if(ST[i].st!=-1)
    {
        if(ST[i].st==0)
            return 0;
        else 
            return (r-l+1);
    }
    
    //
    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)return Query2(l,r,LL(i));
    if(l>mid)return Query2(l,r,RR(i));
    else
    {
        int maxl=Query2(l,mid,LL(i));
        int maxr=Query2(mid+1,r,RR(i));
        return Max(Max(maxl,maxr),Min(mid-l+1,ST[LL(i)].rval1)+Min(r-mid,ST[RR(i)].lval1));
    }
}

int n,m;
int main()
{
    int ca;
    int i;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        Build(1,n,1);

        for(i=0;i<m;i++)
        {
            int a,b,c;
              scanf("%d%d%d",&a,&b,&c);
            if(b>c)
                swap(b,c);
            b++;c++;
            if(a==0)
                update(b,c,0,1);
             else if(a==1)
                update(b,c,1,1);
            else if(a==2)
                Set_Rev(b,c,1);
            else if(a==3)
                printf("%d\n",Query1(b,c,1));
            else
            {
                printf("%d\n",Query2(b,c,1));
            }
        }
    }

    return 0;
}



---------------------------------------------------------------------------------------------------------------------------------------------------------------
调了一整天，一般能想到的数据都过了，但就是不得AC...无语了.... 没测试数据，这题搁浅了...(11月3日)

#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int const maxn=1000010;
#define Max(a,b) ((a>b?a:b))
#define Min(a,b) ((a<b?a:b))

int Lchild(int i) 
{
    return    (i*2);
}

int Rchild(int i)
{
    return (i*2+1);
}
struct node
{
    int sum;//统计1的个数
    int rev;
    int st;
    int cval0,lval0,rval0;//统计最大连续0,左连续0,右连续0
    int cval1,lval1,rval1;//统计最大连续1,左连续1,右连续1
    int l,r;
    void doit()
    {
        if(st==0)
        {
            cval1=lval1=rval1=0;
            cval0=rval0=lval0=len();
            sum=0;
        }
        else if(st==1)
        {
            cval1=lval1=rval1=len();
            cval0=lval0=rval0=0;
            sum=len();
        }
    }
    int len(){return r-l+1;}
}ST[maxn*8];
int a[maxn];//存输入数据

void qufan(int i)
{
    ST[i].sum=ST[i].len()-ST[i].sum;
    swap(ST[i].cval1,ST[i].cval0);
    swap(ST[i].rval1,ST[i].rval0);
    swap(ST[i].lval1,ST[i].lval0);
}


void Build(int l,int r,int i)
{
    ST[i].l=l;
    ST[i].r=r;
    ST[i].rev=0;
    ST[i].st=-1;
    if(l==r)
    {
        //ST[i].st=a[l];
        ST[i].sum=a[l];
        if(a[r]==1)
        {
            ST[i].cval1=ST[i].lval1=ST[i].rval1=1;
            ST[i].cval0=ST[i].lval0=ST[i].rval0=0;
        }
        else
        {
            ST[i].cval1=ST[i].lval1=ST[i].rval1=0;
            ST[i].cval0=ST[i].lval0=ST[i].rval0=1;

        }
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,Lchild(i));
    Build(mid+1,r,Rchild(i));
    ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
    ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
    ST[i].lval0=ST[Lchild(i)].lval0;
    ST[i].rval0=ST[Rchild(i)].rval0;
    if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
        ST[i].lval0+=ST[Rchild(i)].lval0;
    if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
        ST[i].rval0+=ST[Lchild(i)].rval0;
    //////////////////////////////////////////////////////////////////////////

    ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
    ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
    ST[i].lval1=ST[Lchild(i)].lval1;
    ST[i].rval1=ST[Rchild(i)].rval1;
    if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
        ST[i].lval1+=ST[Rchild(i)].lval1;
    if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
        ST[i].rval1+=ST[Lchild(i)].rval1;
    //////////////////////////////////////////////////////////////////////////
    ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
    //////////////////////////////////////////////////////////////////////////

}

void push_down(int i)
{
    if(ST[i].st!=-1)
    {
        ST[Lchild(i)].st=ST[Rchild(i)].st=ST[i].st;
        //ST[Lchild(i)].rev=0;
        //ST[Rchild(i)].rev=0;
    }
    
    if(ST[i].rev==1)
    {
        ST[Lchild(i)].rev^=1;
        ST[Rchild(i)].rev^=1;
        //qufan(Lchild(i));
        //qufan(Rchild(i));
        //ST[i].rev=0;
    }
}



void update(int l,int r,int op,int i)
{
    if(l==ST[i].l&&r==ST[i].r)
    {
        
        ST[i].st=op;
        ST[i].rev=0;
        ST[i].doit();
        return;
    }
    push_down(i);
    if(ST[i].st!=-1)
    {
        ST[Lchild(i)].doit();

    }
    if(ST[i].rev==1)
        qufan(Lchild(i));
    if(ST[i].st!=-1)
    {
        ST[Rchild(i)].doit();
        ST[i].st=-1;
    }

    if(ST[i].rev==1)
    {

        qufan(Rchild(i));
        ST[i].rev=0;
    }

    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)update(l,r,op,Lchild(i));
    else if(l>mid)update(l,r,op,Rchild(i));
    else
    {
        update(l,mid,op,Lchild(i));
        update(mid+1,r,op,Rchild(i));
    }

    ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
    ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
    ST[i].lval0=ST[Lchild(i)].lval0;
    ST[i].rval0=ST[Rchild(i)].rval0;
    if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
        ST[i].lval0+=ST[Rchild(i)].lval0;
    if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
        ST[i].rval0+=ST[Lchild(i)].rval0;
    //////////////////////////////////////////////////////////////////////////

    ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
    ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
    ST[i].lval1=ST[Lchild(i)].lval1;
    ST[i].rval1=ST[Rchild(i)].rval1;
    if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
        ST[i].lval1+=ST[Rchild(i)].lval1;
    if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
        ST[i].rval1+=ST[Lchild(i)].rval1;
    //////////////////////////////////////////////////////////////////////////
    ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
    //////////////////////////////////////////////////////////////////////////
}

void Set_Rev(int l,int r,int i)
{
    if(l==ST[i].l&&r==ST[i].r)
    {
        ST[i].rev^=1;
        qufan(i);
        return;
    }
    push_down(i);
    if(ST[i].st!=-1)
    {
        ST[Lchild(i)].doit();

    }
    if(ST[i].rev==1)
        qufan(Lchild(i));
    if(ST[i].st!=-1)
    {
        ST[Rchild(i)].doit();
        ST[i].st=-1;
    }

    if(ST[i].rev==1)
    {

        qufan(Rchild(i));
        ST[i].rev=0;
    }
    

    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)Set_Rev(l,r,Lchild(i));
    else if(l>mid)Set_Rev(l,r,Rchild(i));
    else
    {
        Set_Rev(l,mid,Lchild(i));
        Set_Rev(mid+1,r,Rchild(i));
    }

    ST[i].cval0=Max(ST[Lchild(i)].cval0,ST[Rchild(i)].cval0);
    ST[i].cval0=Max(ST[i].cval0,ST[Lchild(i)].rval0+ST[Rchild(i)].lval0);
    ST[i].lval0=ST[Lchild(i)].lval0;
    ST[i].rval0=ST[Rchild(i)].rval0;
    if(ST[Lchild(i)].lval0==ST[Lchild(i)].len())
        ST[i].lval0+=ST[Rchild(i)].lval0;
    if(ST[Rchild(i)].rval0==ST[Rchild(i)].len())
        ST[i].rval0+=ST[Lchild(i)].rval0;
    //////////////////////////////////////////////////////////////////////////

    ST[i].cval1=Max(ST[Lchild(i)].cval1,ST[Rchild(i)].cval1);
    ST[i].cval1=Max(ST[i].cval1,ST[Lchild(i)].rval1+ST[Rchild(i)].lval1);
    ST[i].lval1=ST[Lchild(i)].lval1;
    ST[i].rval1=ST[Rchild(i)].rval1;
    if(ST[Lchild(i)].lval1==ST[Lchild(i)].len())
        ST[i].lval1+=ST[Rchild(i)].lval1;
    if(ST[Rchild(i)].rval1==ST[Rchild(i)].len())
        ST[i].rval1+=ST[Lchild(i)].rval1;
    //////////////////////////////////////////////////////////////////////////
    ST[i].sum=ST[Lchild(i)].sum+ST[Rchild(i)].sum;
    //////////////////////////////////////////////////////////////////////////


}

int Query1(int l,int r,int i)//查询[l,r]有多少1
{
    if(ST[i].l==l&&ST[i].r==r)
        return ST[i].sum;

    push_down(i);
    if(ST[i].st!=-1)
    {
        ST[Lchild(i)].doit();

    }
    if(ST[i].rev==1)
        qufan(Lchild(i));
    if(ST[i].st!=-1)
    {
        ST[Rchild(i)].doit();
        ST[i].st=-1;
    }

    if(ST[i].rev==1)
    {

        qufan(Rchild(i));
        ST[i].rev=0;
    }
    

    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)return Query1(l,r,Lchild(i));
    if(l>mid)return Query1(l,r,Rchild(i));
    else{return Query1(l,mid,Lchild(i))+Query1(mid+1,r,Rchild(i));}
}

int Query2(int l,int r,int i)//查[l,r]中最大连续1
{
    if(ST[i].l==l&&ST[i].r==r)
        return ST[i].cval1;
    
    push_down(i);
    if(ST[i].st!=-1)
    {
        ST[Lchild(i)].doit();

    }
    if(ST[i].rev==1)
        qufan(Lchild(i));
    if(ST[i].st!=-1)
    {
        ST[Rchild(i)].doit();
        ST[i].st=-1;
    }

    if(ST[i].rev==1)
    {

        qufan(Rchild(i));
        ST[i].rev=0;
    }
    //
    int mid=(ST[i].l+ST[i].r)>>1;
    if(r<=mid)return Query2(l,r,Lchild(i));
    if(l>mid)return Query2(l,r,Rchild(i));
    else
    {
        int maxl=Query2(l,mid,Lchild(i));
        int maxr=Query2(mid+1,r,Rchild(i));
        return Max(Max(maxl,maxr),Min(mid-l+1,ST[Lchild(i)].rval1)+Min(r-mid,ST[Rchild(i)].lval1));
    }
}

int n,m;
int main()
{
    int ca;
    int i;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        Build(1,n,1);

        for(i=0;i<m;i++)
        {
            int a,b,c;
              scanf("%d%d%d",&a,&b,&c);
            if(b>c)
                swap(b,c);
            b++;c++;
            if(a==0)
                update(b,c,0,1);
             else if(a==1)
                update(b,c,1,1);
            else if(a==2)
                Set_Rev(b,c,1);
            else if(a==3)
                printf("%d\n",Query1(b,c,1));
            else
            {
                printf("%d\n",Query2(b,c,1));
            }
        }
    }

    return 0;
}



PS:谁能说明下上面的代码错在哪？
 

posted on 2010-11-03 00:55 abilitytao 阅读(1205) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理