【题目描述】
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
【输入】
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b)
这题真心烦，尤其是对初学线段树的我来说。考试的时候不得不强行写了30分的程序(o(╯□╰)o)。调了一天了，到晚上才调出来，我果然是蒟蒻。
`此处我用的是姜神的思路，又省空间又省时间，真的好。 nod数组代表lazy，如果下面区间数字一致，
可代表 0or1时：update&pushdown 没什么难度。
2时：+一个如果区间不相等，再往下就是了
3时：查询左右即可。
4时：用一个last数组存储前一个区间的值，更新max即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#define push_up if (nod[rt<<1]==nod[rt<<1|1]&&nod[rt]==-1) nod[rt]=nod[rt<<1]
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int nod[800005],n,m,last,max1,ans,a;
void init()
{
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
}
void pushdown(int rt)
{
if (nod[rt]!=-1)
{
nod[rt<<1]=nod[rt<<1|1]=nod[rt];
nod[rt]=-1;
}
}
void change(int rt,int l,int r,int a,int b,int color)
{
if (a<=l&&b>=r)
{
nod[rt]=color;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if (a<=mid) change(lson,a,b,color);
if (b>mid) change(rson,a,b,color);
push_up;
}
void modity(int rt,int l,int r,int a,int b)
{
if (a<=l&&b>=r)
{
if (nod[rt]!=-1)
{
nod[rt]=1-nod[rt];
return;
}
}
pushdown(rt);
int mid=(l+r)>>1;
if (a<=mid) modity(lson,a,b);
if (b>mid) modity(rson,a,b);
push_up;
}
int count(int rt,int l,int r,int a,int b)
{
if (a<=l&&b>=r)
{
if (nod[rt]==1) return r-l+1;
else if (nod[rt]==0)return 0;
}
pushdown(rt);
int mid=(l+r)>>1;
int x1=0;
int x2=0;
if (a<=mid) x1=count(lson,a,b);
if (b>mid) x2=count(rson,a,b);
push_up;
return x1+x2;
}
void find(int rt,int l,int r,int a,int b)
{
if (a<=l&&b>=r)
{
if (nod[rt]!=-1)
{
if (nod[rt]==1&&last==1)
{
max1+=r-l+1;
ans=max(max1,ans);
}
else if (nod[rt]==1&&last==0)
{
max1=r-l+1;
ans=max(max1,ans);
}
else if (nod[rt]==0)
{
max1=0;
}
ans=max(max1,ans);
last=nod[rt];
return;
}
if (l==r) return;
}
pushdown(rt);
int mid=(l+r)>>1;
if (a<=mid) find(lson,a,b);
if (b>mid) find(rson,a,b);
push_up;
}
void work()
{
cin>>n>>m;
int x,y,z;
for (int i=0;i<n;i++)
{
scanf("%d",&a);
change(1,0,n-1,i,i,a);
}
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if (x==0||x==1) change(1,0,n-1,y,z,x);
if (x==2) modity(1,0,n-1,y,z);
if (x==3) printf("%d\n",count(1,0,n-1,y,z));
if (x==4)
{
last=1;
max1=ans=0;
find(1,0,n-1,y,z);
printf("%d\n",ans);
}
}
}
int main()
{
init();
work();
return 0;
}