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 阅读(1194) 评论(0)  编辑 收藏 引用


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