# The Fourth Dimension Space

## HDOJ 3397 线段树大综合

#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;
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------

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