[HDU-3397]线段树区间修改双lazy维护，好题

题目链接
题意：给定一个01串，操作有区间取反 区间赋1 区间赋0 查询区间1的个数 和连续1的个数。
思路：维护双lazy，注意当置成全0或者全1的时候清空懒标记，如果区间取反那就不要清空懒标记，因为区间取反和前面01序列的取值是有关的。

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
struct node{
   
	int l;
	int r;
	int	lnum0; 
	int lnum;
	int rnum0;
	int rnum;
	int maxnum0;
	int maxnum;
	int cnt1;
	int lz;
	int lzz;
}tr[N<<2];
int a[N];
void pushup(int u)
{
   
	tr[u].cnt1=tr[u<<1].cnt1+tr[u<<1|1].cnt1;
	tr[u].lnum=(tr[u<<1].lnum==(tr[u<<1].r-tr[u<<1].l+1)) ? tr[u<<1].lnum+tr[u<<1|1].lnum:tr[u<<1].lnum;
	tr[u].rnum=(tr[u<<1|1].rnum==(tr[u<<1|1].r-tr[u<<1|1].l+1) ?	tr[u<<1].rnum+tr[u<<1|1].rnum:tr[u<<1|1].rnum );
	tr[u].maxnum=(max(tr[u<<1].maxnum,tr[u<<1|1].maxnum));
	tr[u].maxnum=max(tr[u].maxnum,tr[u<<1].rnum+tr[u<<1|1].lnum);
	tr[u].lnum0=(tr[u<<1].lnum0==(tr[u<<1].r-tr[u<<1].l+1))? tr[u<<1].lnum0+tr[u<<1|1].lnum0:tr[u<<1].lnum0;
	tr[u].rnum0=(tr[u<<1|1].rnum0==(tr[u<<1|1].r-tr[u<<1|1].l+1))?	tr[u<<1].rnum0+tr[u<<1|1].rnum0:tr[u<<1|1].rnum0;
	tr[u].maxnum0=max(tr[u<<1].maxnum0,tr[u<<1|1].maxnum0);
	tr[u].maxnum0=max(tr[u].maxnum0,tr[u<<1].rnum0+tr[u<<1|1].lnum0);
}
void ff(node &u)
{
   	
	u.cnt1=u.r-u.l+1-u.cnt1; 
	swap(u.lnum,u.lnum0);
	swap(u.rnum,u.rnum0);
	swap(u.maxnum,u.maxnum0);
}
void pushdown(int u)
{
   
	if(tr[u].lzz!=-1)
	{
   
		tr[u<<1].lzz=tr[u<<1|1].lzz=tr[u].lzz;
		tr[u<<1].lz=tr[u<<1|1].lz=0;
		tr[u].lzz=-1;
		int r1,r2;
		if(tr[u<<1].lzz==0)
		r1=0,r2=1;
		else
		r1=1,r2=0;
		tr[u<<1].lnum=tr[u<<1].rnum=tr[u<<1].cnt1=tr[u<<1].maxnum=r1*(tr[u<<1].r-tr[u<<1].l+1);
		tr[u<<1|1].lnum=tr[u<<1|1].rnum=tr[u<<1|1].cnt1=tr[u<<1|1].maxnum=r1*(tr[u<<1|1].r-tr[u<<1|1].l+1);
		tr[u<<1].lnum0=tr[u<<1].rnum0=tr[u<<1].maxnum0=r2*(tr[u<<1].r-tr[u<<1].l+1);
		tr[u<<1|1].lnum0=tr[u<<1|1].rnum0=tr[u<<1|1].maxnum0=r2*(tr[u<<1|1].r-tr[u<<1|1].l+1);
	}
	if(tr[u].lz)
	{
   
		tr[u<<1].lz^=1;
		tr[u<<1|1].lz^=1;
		tr[u].lz=0;
		ff(tr[u<<1]);
		ff(tr[u<<1|1]);
	}
}
void build(int u,int l,int r)
{
   
	tr[u]={
   l,r,0,0,0,0,0,0,0,0,-1};
	if(l==r)
	{
   
	 	if(a[l]==1)
	 		tr[u].lnum=tr[u].rnum=tr[u].maxnum=tr[u].cnt1=1;
	 	else
	 		tr[u].lnum0=tr[u].rnum0=tr[u].maxnum0=1;
	 	return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}
void mdf(int u,int l,int r,int d)
{
   
	if(tr[u].l>=l && tr[u].r<=r)
	{
   
		if(d==0 || d==1)
		{
   
			tr[u].lzz=d;
			tr[u].lz=0;
			tr[u].lnum=tr[u].rnum=tr[u].maxnum=tr[u].cnt1=d*(tr[u].r-tr[u].l+1);
			tr[u].lnum0=tr[u].rnum0=tr[u].maxnum0=(d^1)*(tr[u].r-tr[u].l+1);
		}
		else if(d==2)
		{
   
			tr[u].lz^=1;
			tr[u].cnt1=tr[u].r-tr[u].l+1-tr[u].cnt1;
			swap(tr[u].lnum,tr[u].lnum0);
			swap(tr[u].rnum,tr[u].rnum0);
			swap(tr[u].maxnum,tr[u].maxnum0);
		}
		return ;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid)
		mdf(u<<1,l,r,d);
	if(r>mid)
		mdf(u<<1|1,l,r,d);
		pushup(u);
}
node qr(int u,int l,int r)
{
   
	if(tr[u].l>=l && tr[u].r<=r)
	return tr[u];
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid)
	return qr(u<<1,l,r);
	if(l>mid)
	return qr(u<<1|1,l,r);
	node t1=qr(u<<1,l,r),t2=qr(u<<1|1,l,r);
	node res;
	res.cnt1=t1.cnt1 + t2.cnt1;
	res.lnum=(t1.lnum==(t1.r-t1.l+1))?(t1.lnum+t2.lnum):t1.lnum;
	res.rnum=(t2.rnum==(t2.r-t2.l+1))?(t2.rnum+t1.rnum):t2.rnum;
	res.maxnum=max(t1.maxnum,t2.maxnum);
	res.maxnum=max(res.maxnum,t1.rnum+t2.lnum);
	return	res;
}
int main()
{
   
	int t;
	cin>>t;
	while(t--)
	{
   
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		build(1,1,n);
		int op,l,r;
		while(m--)
		{
   	
			scanf("%d%d%d",&op,&l,&r);
			l++,r++;
			if(op==0)
			{
   
				mdf(1,l,r,0);
			}
			else if(op==1)
			{
   
				mdf(1,l,r,1);
			}
			else if(op==2)
			{
   
				mdf(1,l,r,2);
			}
			else if(op==3)
			{
   
				node R=qr(1,l,r);
				printf("%d\n",R.cnt1);
			}
			else
			{
   
				node R=qr(1,l,r);
				printf("%d\n",R.maxnum);
			}	
		}
	}
	return 0;
}