在dls的数据结构中级课那学了最大字段和的线段树写法，对于这道题，我们要维护的信息有：
- 区间左边0/1的个数，
- 区间右边0/1的个数
- 区间最长0/1的长度
- 区间的赋值标记
- 区间的取反标记
- 整个区间的长度
- 对于 1 ~ 4 是很基本的最大字段和操作
- 对于 两种不同的标记，打标记是有时间顺序的，区间赋0/1，可以覆盖区间取反的标记，而区间取反的标记是在区间赋0/1的基础上进行的，标记下传也要先下传区间赋0/1的标记，再下传区间取反的标记。
struct info
{
int s0,ls0,rs0,ms0,s1,ls1,rs1,ms1;
};
info operator +(const info &a,const info &b)
{
info t;
t.s0=a.s0+b.s0;
t.s1=a.s1+b.s1;
t.ls0=a.ls0;
t.ls1=a.ls1;
t.rs0=b.rs0;
t.rs1=b.rs1;
int asz=a.s0+a.s1;
int bsz=b.s0+b.s1;
if(a.ls0==asz)
t.ls0=asz+b.ls0;
if(b.rs0==bsz)
t.rs0=bsz+a.rs0;
if(a.ls1==asz)
t.ls1=asz+b.ls1;
if(b.rs1==bsz)
t.rs1=bsz+a.rs1;
t.ms0=max({a.ms0,b.ms0,a.rs0+b.ls0});
t.ms1=max({a.ms1,b.ms1,a.rs1+b.ls1});
return t;
}
struct segtree
{
struct info val;
int sz,tag1,tag2;
}seg[N*4];
void update(int id)
{
seg[id].val=seg[id*2].val+seg[id*2+1].val;
}
void settag(int id,int tag)
{
int sz=seg[id].sz;
if(tag==0)
{
seg[id].tag2=0,seg[id].tag1=0;
seg[id].val={sz,sz,sz,sz,0,0,0,0};
}
else if(tag==1)
{
seg[id].tag2=0,seg[id].tag1=1;
seg[id].val={0,0,0,0,sz,sz,sz,sz};
}
if(tag==2)
{
seg[id].tag2^=1;
swap(seg[id].val.s0,seg[id].val.s1);
swap(seg[id].val.ls0,seg[id].val.ls1);
swap(seg[id].val.rs0,seg[id].val.rs1);
swap(seg[id].val.ms0,seg[id].val.ms1);
}
}
void pushdown(int id)
{
if(seg[id].tag1!=-1)
settag(id*2,seg[id].tag1),
settag(id*2+1,seg[id].tag1);
if(seg[id].tag2)
settag(id*2,2),
settag(id*2+1,2);
seg[id].tag1=-1,seg[id].tag2=0;
}
void build(int id,int l,int r)
{
seg[id].sz=r-l+1;
seg[id].tag1=-1,seg[id].tag2=0;
if(l==r)
{
int x; cin>>x;
if(x==0)
seg[id].val={1,1,1,1,0,0,0,0};
else seg[id].val={0,0,0,0,1,1,1,1};
return;
}
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
update(id);
}
void modify(int id,int l,int r,int ql,int qr,int tag)
{
if(l==ql&&r==qr)
{
settag(id,tag);
return;
}
pushdown(id);
int mid=(l+r)>>1;
if(qr<=mid)
modify(id*2,l,mid,ql,qr,tag);
else if(ql>mid)
modify(id*2+1,mid+1,r,ql,qr,tag);
else
modify(id*2,l,mid,ql,mid,tag),
modify(id*2+1,mid+1,r,mid+1,qr,tag);
update(id);
}
info query(int id,int l,int r,int ql,int qr)
{
if(ql==l&&qr==r)
{
return seg[id].val;
}
pushdown(id);
int mid=(l+r)>>1;
if(qr<=mid)
return query(id*2,l,mid,ql,qr);
else if(ql>mid)
return query(id*2+1,mid+1,r,ql,qr);
else return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
}
void solve()
{
int n,q; cin>>n;
cin>>q;
build(1,1,n);
for(int i=1;i<=q;i++)
{
int op,l,r; cin>>op>>l>>r;
l++,r++;
if(op<=2)
{
modify(1,1,n,l,r,op);
}
else
{
if(op==3)
cout<<query(1,1,n,l,r).s1<<endl;
else
cout<<query(1,1,n,l,r).ms1<<endl;
}
}
return;
}