[文章目录]
Description
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 4 a b 询问[a, b]区间内最多有多少个连续的1 对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
啊，幸福来得太突然，还没有大的输出调试就把肉眼编译过的交上去了，A啦哈哈哈哈哈哈哈哈。
额，属于看着都会，写不对，贼难调那类的大恶心线段树。
打的时候注意一下三个lazy的关系，没错，三个。然后维护的参数是。。8个，嗯，就这样：）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ls pos<<1
#define rs pos<<1|1
#define N 101000
using namespace std;
int n,m,w[N];
struct seg
{
int sum1[N<<2],sum0[N<<2],mx1[N<<2],mx0[N<<2];
int mx1l[N<<2],mx0l[N<<2],mx1r[N<<2],mx0r[N<<2];
bool lz1[N<<2],lz0[N<<2],lzyh[N<<2];
void pushup(int pos)
{
sum1[pos]=sum1[ls]+sum1[rs];
sum0[pos]=sum0[ls]+sum0[rs];
mx1[pos]=max(max(mx1[ls],mx1[rs]),mx1r[ls]+mx1l[rs]);
mx0[pos]=max(max(mx0[ls],mx0[rs]),mx0r[ls]+mx0l[rs]);
mx0l[pos]= sum1[ls]==0 ? sum0[ls]+mx0l[rs] : mx0l[ls];
mx1l[pos]= sum0[ls]==0 ? sum1[ls]+mx1l[rs] : mx1l[ls];
mx0r[pos]= sum1[rs]==0 ? sum0[rs]+mx0r[ls] : mx0r[rs];
mx1r[pos]= sum0[rs]==0 ? sum1[rs]+mx1r[ls] : mx1r[rs];
}
void pushdown(int pos)
{
if(lz1[pos])
{
lz0[ls]=lzyh[ls]=0; lz1[ls]=1;
sum1[ls]+=sum0[ls]; sum0[ls]=0;
mx1l[ls]=mx1r[ls]=mx1[ls]=sum1[ls];
mx0l[ls]=mx0r[ls]=mx0[ls]=0;
lz0[rs]=lzyh[rs]=0; lz1[rs]=1;
sum1[rs]+=sum0[rs]; sum0[rs]=0;
mx1l[rs]=mx1r[rs]=mx1[rs]=sum1[rs];
mx0l[rs]=mx0r[rs]=mx0[rs]=0;
lz1[pos]=0;
}
if(lz0[pos])
{
lz1[ls]=lzyh[ls]=0; lz0[ls]=1;
sum0[ls]+=sum1[ls]; sum1[ls]=0;
mx0l[ls]=mx0r[ls]=mx0[ls]=sum0[ls];
mx1l[ls]=mx1r[ls]=mx1[ls]=0;
lz1[rs]=lzyh[rs]=0; lz0[rs]=1;
sum0[rs]+=sum1[rs]; sum1[rs]=0;
mx0l[rs]=mx0r[rs]=mx0[rs]=sum0[rs];
mx1l[rs]=mx1r[rs]=mx1[rs]=0;
lz0[pos]=0;
}
if(lzyh[pos])
{
swap(lz0[ls],lz1[ls]);swap(sum0[ls],sum1[ls]);
swap(mx1l[ls],mx0l[ls]);swap(mx1r[ls],mx0r[ls]);
swap(mx1[ls],mx0[ls]);if(!lz0[ls]&&!lz1[ls]) lzyh[ls]^=1;
swap(lz0[rs],lz1[rs]);swap(sum0[rs],sum1[rs]);
swap(mx1l[rs],mx0l[rs]);swap(mx1r[rs],mx0r[rs]);
swap(mx1[rs],mx0[rs]);if(!lz0[rs]&&!lz1[rs]) lzyh[rs]^=1;
lzyh[pos]=0;
}
}
void build(int pos,int l,int r)
{
if(l==r)
{
if(w[l]) sum1[pos]=mx1[pos]=mx1l[pos]=mx1r[pos]=1;
else sum0[pos]=mx0[pos]=mx0l[pos]=mx0r[pos]=1;
return ;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(pos);
}
void fix0(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
lz1[pos]=lzyh[pos]=0; lz0[pos]=1;
sum0[pos]+=sum1[pos]; sum1[pos]=0;
mx0l[pos]=mx0r[pos]=mx0[pos]=sum0[pos];
mx1l[pos]=mx1r[pos]=mx1[pos]=0;
return ;
}
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) fix0(ls,l,mid,x,y);
else if(x>mid) fix0(rs,mid+1,r,x,y);
else fix0(ls,l,mid,x,y),fix0(rs,mid+1,r,x,y);
pushup(pos);
}
void fix1(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
lz0[pos]=lzyh[pos]=0; lz1[pos]=1;
sum1[pos]+=sum0[pos]; sum0[pos]=0;
mx1l[pos]=mx1r[pos]=mx1[pos]=sum1[pos];
mx0l[pos]=mx0r[pos]=mx0[pos]=0;
return ;
}
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) fix1(ls,l,mid,x,y);
else if(x>mid) fix1(rs,mid+1,r,x,y);
else fix1(ls,l,mid,x,y),fix1(rs,mid+1,r,x,y);
pushup(pos);
}
void fixyh(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
swap(lz0[pos],lz1[pos]);swap(sum0[pos],sum1[pos]);
swap(mx1l[pos],mx0l[pos]);swap(mx1r[pos],mx0r[pos]);
swap(mx1[pos],mx0[pos]);if(!lz0[pos]&&!lz1[pos]) lzyh[pos]^=1;
return ;
}
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) fixyh(ls,l,mid,x,y);
else if(x>mid) fixyh(rs,mid+1,r,x,y);
else fixyh(ls,l,mid,x,y),fixyh(rs,mid+1,r,x,y);
pushup(pos);
}
int query_sum(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) {return sum1[pos];}
int mid=l+r>>1;
pushdown(pos);
if(y<=mid) return query_sum(ls,l,mid,x,y);
else if(x>mid) return query_sum(rs,mid+1,r,x,y);
else return query_sum(ls,l,mid,x,y)+query_sum(rs,mid+1,r,x,y);
}
int getleft(int pos,int l,int r,int y)
{
if(y>=r) return mx1l[pos];
pushdown(pos);
int mid=l+r>>1;
if(y<=mid) return getleft(ls,l,mid,y);
else if(sum0[ls]==0) return sum1[ls]+getleft(rs,mid+1,r,y);
else return getleft(ls,l,mid,y);
}
int getright(int pos,int l,int r,int y)
{
if(y<=l) return mx1r[pos];
pushdown(pos);
int mid=l+r>>1;
if(y>mid) return getright(rs,mid+1,r,y);
else if(sum0[rs]==0) return sum1[rs]+getright(ls,l,mid,y);
else return getright(rs,mid+1,r,y);
}
int query_mx(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) {return mx1[pos];}
int mid=l+r>>1;
pushdown(pos);
if(y<=mid) return query_mx(ls,l,mid,x,y);
else if(x>mid) return query_mx(rs,mid+1,r,x,y);
else return max(max(query_mx(ls,l,mid,x,y),query_mx(rs,mid+1,r,x,y)),getright(ls,l,mid,x)+getleft(rs,mid+1,r,y));
}
}T;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
T.build(1,1,n);
int sw,ll,rr;
while(m--)
{
scanf("%d%d%d",&sw,&ll,&rr);ll++,rr++;
switch(sw)
{
case 0:T.fix0(1,1,n,ll,rr);break;
case 1:T.fix1(1,1,n,ll,rr);break;
case 2:T.fixyh(1,1,n,ll,rr);break;
case 3:printf("%d\n",T.query_sum(1,1,n,ll,rr));break;
case 4:printf("%d\n",T.query_mx(1,1,n,ll,rr));break;
}
}
return 0;
}