题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1858
线段树...调了一个上午...(后面带 // 的都是改出来的)
lazy 标记的下放好麻烦，还得考虑赋值和取反的先后顺序什么的...
因为在取反时把赋值标记 swap 了，所以下放的时候先判断取反再判断赋值...
而且WA了一上午的原因竟然是一开始不慎把取反以为成翻转了，后来没改干净...那个 rev 的名字啊...
总之没有太改变自己最初的想法、改了些细节就A了还是很高兴的！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=1e5+;
int n,m,op,a,b,c[maxn];
struct N{
int sum,z[],y[],m[];
int lz[],rev,len;
}t[maxn<<];
int rd()
{
int ret=;char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return ret;
}
void pushup(int x)
{
int ls=(x<<),rs=(x<<|);
t[x].sum=t[ls].sum+t[rs].sum;
for(int i=;i<=;i++)
{
t[x].z[i]=t[ls].z[i]+(t[ls].z[i]==t[ls].len?t[rs].z[i]:);
t[x].y[i]=t[rs].y[i]+(t[rs].y[i]==t[rs].len?t[ls].y[i]:);
// t[x].m[i]=max(max(t[x].z[i],t[x].y[i]),t[ls].y[i]+t[rs].z[i]);//
t[x].m[i]=max(max(t[ls].m[i],t[rs].m[i]),t[ls].y[i]+t[rs].z[i]);//
}
}
void upt(int x,int val)//赋值
{
t[x].lz[val]=;
t[x].lz[!val]=; t[x].rev=;//!
t[x].sum=t[x].len*val;
t[x].z[val]=t[x].y[val]=t[x].m[val]=t[x].len;
t[x].z[!val]=t[x].y[!val]=t[x].m[!val]=;
}
void re(int x)//取反
{
swap(t[x].z[],t[x].z[]); swap(t[x].y[],t[x].y[]);//!!!
swap(t[x].m[],t[x].m[]);
t[x].sum=t[x].len-t[x].sum; t[x].rev^=;
swap(t[x].lz[],t[x].lz[]);//!
}
void pushdown(int x)
{
// if(t[x].len==1)return;//
int ls=(x<<),rs=(x<<|);
if(t[x].rev)t[x].rev^=,re(ls),re(rs);
for(int v=;v<=;v++)
if(t[x].lz[v])t[x].lz[v]=,upt(ls,v),upt(rs,v);//顺序
}
void build(int x,int l,int r)
{
t[x].len=r-l+;
if(l==r)
{
t[x].z[c[l]]=t[x].y[c[l]]=t[x].m[c[l]]=;
t[x].sum=c[l]; //
return;
}
int mid=((l+r)>>);
build(x<<,l,mid); build(x<<|,mid+,r);
pushup(x);
}
void update(int x,int l,int r,int L,int R,int val)
{
if(l>=L&&r<=R)
{
upt(x,val);return;
}
pushdown(x);
int mid=((l+r)>>);
if(mid>=L)update(x<<,l,mid,L,R,val);
if(mid<R)update(x<<|,mid+,r,L,R,val);
pushup(x);
}
void rever(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)
{
re(x);return;
}
int mid=((l+r)>>);
pushdown(x);
if(mid>=L)rever(x<<,l,mid,L,R);
if(mid<R)rever(x<<|,mid+,r,L,R);
pushup(x);
}
int query(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return t[x].sum;
int mid=((l+r)>>),ret=;
pushdown(x);
if(mid>=L)ret+=query(x<<,l,mid,L,R);
if(mid<R)ret+=query(x<<|,mid+,r,L,R);
return ret;
}
int ask(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return t[x].m[];
pushdown(x);//
int mid=((l+r)>>);
if(mid>=R)return ask(x<<,l,mid,L,R);
if(mid<L)return ask(x<<|,mid+,r,L,R);
int ret=;
ret=max(ask(x<<,l,mid,L,R),ask(x<<|,mid+,r,L,R));
ret=max(ret,min(t[x<<].y[],mid-L+)+min(t[x<<|].z[],R-mid));
return ret;
}
int main()
{
n=rd();m=rd();
for(int i=;i<=n;i++)c[i]=rd();
build(,,n);
while(m--)
{
op=rd(); a=rd()+; b=rd()+;
if(op==||op==)update(,,n,a,b,op);
if(op==)rever(,,n,a,b);
if(op==)printf("%d\n",query(,,n,a,b));
if(op==)printf("%d\n",ask(,,n,a,b));
}
return ;
}