线段树......模板题(雾？
然而两种标记会互相影响，必须保证每次只放一个(不然就不知道怎么放了)，具体的影响就是：
翻转标记会使得覆盖标记一起翻转，下放的时候就是各种swap
覆盖标记会抹掉翻转标记，下放的时候好像挺正常的
然后就是码码码+细节
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a{int ll,rr,vv;};
int val[*N],last[*N][],lst[*N][],rst[*N][];
int num[N],laz1[*N],laz2[*N];
int n,m,t1,t2,t3;
void pushup(int nde,int l,int r)
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
val[nde]=val[ls]+val[rs];
//value
lst[nde][]=(last[ls][]==mid-l+)?last[ls][]+lst[rs][]:lst[ls][];
rst[nde][]=(last[rs][]==r-mid)?last[rs][]+rst[ls][]:rst[rs][];
last[nde][]=max(rst[ls][]+lst[rs][],max(last[ls][],last[rs][]));
//longest continuing one
lst[nde][]=(last[ls][]==mid-l+)?last[ls][]+lst[rs][]:lst[ls][];
rst[nde][]=(last[rs][]==r-mid)?last[rs][]+rst[ls][]:rst[rs][];
last[nde][]=max(rst[ls][]+lst[rs][],max(last[ls][],last[rs][]));
//longest continuing zero
}
void create(int nde,int l,int r)
{
if(l==r)
{
last[nde][]=lst[nde][]=rst[nde][]=(num[l]^);
val[nde]=last[nde][]=lst[nde][]=rst[nde][]=num[l];
}
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
create(ls,l,mid),create(rs,mid+,r);
pushup(nde,l,r);
}
}
void release(int nde,int l,int r)
{
int mid=(l+r)/,ls=*nde,rs=*nde+;
if(laz2[nde])
{
if(~laz1[ls]) laz1[ls]^=; else laz2[ls]^=;
if(~laz1[rs]) laz1[rs]^=; else laz2[rs]^=;
val[ls]=(mid-l+)-val[ls],val[rs]=(r-mid)-val[rs];
//reversing
swap(last[ls][],last[ls][]),swap(last[rs][],last[rs][]);
swap(lst[ls][],lst[ls][]),swap(lst[rs][],lst[rs][]);
swap(rst[ls][],rst[ls][]),swap(rst[rs][],rst[rs][]);
//a lot of swaps......
laz2[nde]=;
//refresh
}
//release the lazy tag of intervals reversing
else if(~laz1[nde])
{
laz1[ls]=laz1[nde],laz1[rs]=laz1[nde],laz2[ls]=,laz2[rs]=;
//to the left/right son
val[ls]=last[ls][]=lst[ls][]=rst[ls][]=(mid-l+)*laz1[nde];
val[rs]=last[rs][]=lst[rs][]=rst[rs][]=(r-mid)*laz1[nde];
//longest continuing one
last[ls][]=lst[ls][]=rst[ls][]=(mid-l+)*(laz1[nde]^);
last[rs][]=lst[rs][]=rst[rs][]=(r-mid)*(laz1[nde]^);
//longest continuing zero
laz1[nde]=-;
//refresh
}
//release the lazy tag of intervals covering
}
void Change(int nde,int l,int r,int nl,int nr,int task)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
{
last[nde][]=lst[nde][]=rst[nde][]=(task^)*(r-l+);
val[nde]=last[nde][]=lst[nde][]=rst[nde][]=task*(r-l+);
laz1[nde]=task,laz2[nde]=;
}
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
Change(ls,l,mid,nl,nr,task),Change(rs,mid+,r,nl,nr,task);
pushup(nde,l,r);
}
}
void Reverse(int nde,int l,int r,int nl,int nr)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
{
val[nde]=(r-l+)-val[nde],swap(last[nde][],last[nde][]);
swap(lst[nde][],lst[nde][]),swap(rst[nde][],rst[nde][]);
if(~laz1[nde]) laz1[nde]^=; else laz2[nde]^=;
}
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
Reverse(ls,l,mid,nl,nr),Reverse(rs,mid+,r,nl,nr); pushup(nde,l,r);
}
}
int Vquery(int nde,int l,int r,int nl,int nr)
{
if(l>nr||r<nl)
return ;
else if(l>=nl&&r<=nr)
return val[nde];
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
return Vquery(ls,l,mid,nl,nr)+Vquery(rs,mid+,r,nl,nr);
}
}
a Lquery(int nde,int l,int r,int nl,int nr)
{
if(l>=nl&&r<=nr)
return (a){lst[nde][],rst[nde][],last[nde][]};
else
{
int mid=(l+r)/,ls=*nde,rs=*nde+; release(nde,l,r);
if(nr<=mid) return Lquery(ls,l,mid,nl,nr);
if(nl>mid) return Lquery(rs,mid+,r,nl,nr);
a Q1=Lquery(ls,l,mid,nl,nr),Q2=Lquery(rs,mid+,r,nl,nr),ret;
ret.vv=max(max(Q1.vv,Q2.vv),Q1.rr+Q2.ll);
ret.ll=(Q1.vv==(mid-l+))?Q1.vv+Q2.ll:Q1.ll;
ret.rr=(Q2.vv==(r-mid))?Q2.vv+Q1.rr:Q2.rr;
return ret;
}
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
create(,,n);
memset(laz1,-,sizeof laz1);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&t3),t2++,t3++;
if(!t1) Change(,,n,t2,t3,);
else if(t1==) Change(,,n,t2,t3,);
else if(t1==) Reverse(,,n,t2,t3);
else if(t1==) printf("%d\n",Vquery(,,n,t2,t3));
else printf("%d\n",Lquery(,,n,t2,t3).vv);
}
return ;
}