题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1858
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
Input
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目 第二行包括n个数，表示序列的初始状态 接下来m行，每行3个数，op, a, b，（0 < = op < = 4，0 < = a < = b）
Output
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
Sample Input
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
Sample Output
2
6
5
HINT
对于30%的数据，1<=n, m<=1000 对于100%的数据，1< = n, m < = 100000
题解：
考虑怎么对标记进行维护，使用full标记判断该节点所代表的区间是否是同一数字；c标记代表0/1操作，将该节点全部赋值，同时更新full标记
在翻转标记rev的下推过程中注意偶数次翻转等于没有操作，而赋值操作会清空rev标记。在程序中我们考虑另写一个color函数来将节点染色（全部赋值一个数）
关键之处在于合并，对于连续的1的个数其实很好维护，细节在于l0,l1,r0,r1即从区间左边到右边和右边到左边有多少个连续的1；值得注意的是合并操作返回的是一颗子树
那么在统计最大连续的1的时候，我们不能采取累加的方式，而是要在指定区间里合并出一颗新的树，直接输出它的mx1，即最大的连续1的个数
笔者强调，本题细节较多，请读者耐心阅读并尝试自己打完代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int n,m;
int a[N];
struct seg
{
int l,r;
int l0,l1,r0,r1,mx0,mx1,sum0,sum1;
int rev,c,full;
}t[N<<];
void rev(int k)
{
swap(t[k].l0,t[k].l1);
swap(t[k].r0,t[k].r1);
swap(t[k].mx0,t[k].mx1);
swap(t[k].sum0,t[k].sum1);
if(t[k].full!=-)t[k].full^=;
}
void color(int k,int v)
{
t[k].rev=;
int s=t[k].r-t[k].l+;
if(v==)
{
t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=s;
t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=;
}
else
{
t[k].sum0=t[k].l0=t[k].r0=t[k].mx0=;
t[k].sum1=t[k].l1=t[k].r1=t[k].mx1=s;
}
t[k].full=v;
}
seg merge(seg a,seg b)
{
seg tmp;tmp.l=a.l;tmp.r=b.r;
tmp.rev=;tmp.c=-;
tmp.l0=a.l0;tmp.l1=a.l1;
tmp.r0=b.r0;tmp.r1=b.r1;
tmp.mx0=max(a.mx0,b.mx0);
tmp.mx1=max(a.mx1,b.mx1);
tmp.mx0=max(tmp.mx0,a.r0+b.l0);
tmp.mx1=max(tmp.mx1,a.r1+b.l1);
tmp.sum0=a.sum0+b.sum0;
tmp.sum1=a.sum1+b.sum1;
if(a.full==)tmp.l0=a.mx0+b.l0;
else if(a.full==)tmp.l1=a.mx1+b.l1;
if(b.full==)tmp.r0=b.mx0+a.r0;
else if(b.full==)tmp.r1=b.mx1+a.r1;
if(a.full==b.full)
tmp.full=a.full;
else tmp.full=-;
return tmp;
}
void pushup(int k)
{
t[k]=merge(t[k<<],t[k<<|]);
}
void pushdown(int k)
{
if(t[k].l==t[k].r)return;
if(t[k].c!=-)
{
t[k<<].c=t[k<<|].c=t[k].c;
color(k<<,t[k].c);color(k<<|,t[k].c);
t[k].c=-;
}
if(t[k].rev)
{
t[k<<].rev^=;
t[k<<|].rev^=;
rev(k<<);rev(k<<|);
t[k].rev=;
}
}
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;
t[k].c=-;
if(l==r)
{
t[k].full=a[l];
if(t[k].full)
{t[k].l1=t[k].r1=t[k].mx1=t[k].sum1=;}
else
{t[k].l0=t[k].r0=t[k].mx0=t[k].sum0=;}
return;
}
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
pushup(k);
}
void change(int k,int x,int y,int v)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&r==y)
{
color(k,v);
t[k].c=v;
return;
}
int mid=(l+r)>>;
if(mid>=y)change(k<<,x,y,v);
else if(mid<x)change(k<<|,x,y,v);
else
{
change(k<<,x,mid,v);
change(k<<|,mid+,y,v);
}
pushup(k);
}
void rever(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&r==y)
{
rev(k);
t[k].rev=;
return;
}
int mid=(l+r)>>;
if(mid>=y)rever(k<<,x,y);
else if(mid<x)rever(k<<|,x,y);
else
{
rever(k<<,x,mid);
rever(k<<|,mid+,y);
}
pushup(k);
}
seg ask(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r)return t[k];
int mid=(l+r)>>;
if(mid>=y)return ask(k<<,x,y);
else if(mid<x)return ask(k<<|,x,y);
else return merge(ask(k<<,x,mid),ask(k<<|,mid+,y));
}
int asksum(int k,int x,int y)
{
pushdown(k);
int l=t[k].l,r=t[k].r;
if(l==x&&y==r)return t[k].sum1;
int mid=(l+r)>>;
if(mid>=y)return asksum(k<<,x,y);
else if(mid<x)return asksum(k<<|,x,y);
else return asksum(k<<,x,mid)+asksum(k<<|,mid+,y);
}
int main()
{
//freopen("a.in","r",stdin);
//freopen("b.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
build(,,n);
for(int i=;i<=m;i++)
{
int f,x,y;
scanf("%d%d%d",&f,&x,&y);
x++;y++;
switch(f)
{
case :change(,x,y,);break;
case :change(,x,y,);break;
case :rever(,x,y);break;
case :printf("%d\n",asksum(,x,y));break;
case :printf("%d\n",ask(,x,y).mx1);break;
}
}
return ;
}