其实和小白逛公园差不多，编写代码的难度远大于思路难度，难点是调试：
- 注意在区间异或 \(1\) 的时候分清代码里的 最长连续 \(1\) 的长度 和 \(1\) 的个数 。
- 注意查询最长 \(1\) 的时候要用结构体上传，如果用到了定值
len的话要赋值。 - 注意如果只用一个
tag的话，遇到区间异或要对原先tag的情况分类讨论。
点击查看代码
#include<bits/stdc++.h>
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 100050
struct node {
int l0,r0,mx0;
int l1,r1,mx1,cnt1;
int tag;
int len;
}tr[maxn<<2];
int n,m;
int a[maxn];
void cg1(node &x,int a1,int a2,int a3) {
x.l0=a1,x.r0=a2,x.mx0=a3;
}
void cg2(node &x,int a1,int a2,int a3,int a4) {
x.l1=a1,x.r1=a2,x.mx1=a3,x.cnt1=a4;
}
void cg3(node &x,int a1) {
x.tag=a1;
}
void modi(node &x,node y,node z) {
if(y.l0==y.len) x.l0=y.len+z.l0;
else x.l0=y.l0;
if(z.r0==z.len) x.r0=z.len+y.r0;
else x.r0=z.r0;
x.mx0=max(max(y.mx0,z.mx0),y.r0+z.l0);
if(y.l1==y.len) x.l1=y.len+z.l1;
else x.l1=y.l1;
if(z.r1==z.len) x.r1=z.len+y.r1;
else x.r1=z.r1;
x.mx1=max(max(y.mx1,z.mx1),y.r1+z.l1);
x.cnt1=y.cnt1+z.cnt1;
}
void push_up(int idx) { modi(tr[idx],tr[lc(idx)],tr[rc(idx)]); }
void push_down(int idx) {
node &x=tr[idx],&l=tr[lc(idx)],&r=tr[rc(idx)];
if(x.tag==0) return ;
if(x.tag==1) {
int sz=l.len;
cg1(l,sz,sz,sz);
cg2(l,0,0,0,0);
cg3(l,1);
sz=r.len;
cg1(r,sz,sz,sz);
cg2(r,0,0,0,0);
cg3(r,1);
} else if (x.tag==2) {
int sz=l.len;
cg1(l,0,0,0);
cg2(l,sz,sz,sz,sz);
cg3(l,2);
sz=r.len;
cg1(r,0,0,0);
cg2(r,sz,sz,sz,sz);
cg3(r,2);
} else {
node L=l,R=r;
cg1(l,L.l1,L.r1,L.mx1);
cg2(l,L.l0,L.r0,L.mx0,L.len-L.cnt1);
if(l.tag==1) l.tag=2;
else if(l.tag==2) l.tag=1;
else if(l.tag==3) l.tag=0;
else l.tag=3;
cg1(r,R.l1,R.r1,R.mx1);
cg2(r,R.l0,R.r0,R.mx0,R.len-R.cnt1);
if(r.tag==1) r.tag=2;
else if(r.tag==2) r.tag=1;
else if(r.tag==3) r.tag=0;
else r.tag=3;
}
x.tag=0;
}
void build(int idx,int l,int r) {
if(l==r) {
tr[idx].len=1;
if(a[l]==1) cg2(tr[idx],1,1,1,1);
else cg1(tr[idx],1,1,1);
return ;
}
int mid=(l+r)>>1;
build(lc(idx),l,mid);
build(rc(idx),mid+1,r);
tr[idx].len=r-l+1;
push_up(idx);
// cout<<idx<<' '<<tr[idx].cnt1<<'\n';
}
int query_cnt(int idx,int l,int r,int L,int R) {
// cout<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<tr[idx].cnt1<<'\n';
if(L<=l&&r<=R) return tr[idx].cnt1;
push_down(idx);
int mid=(l+r)>>1,res=0;
if(L<=mid) res+=query_cnt(lc(idx),l,mid,L,R);
if(R>mid) res+=query_cnt(rc(idx),mid+1,r,L,R);
return res;
}
node query(int idx,int l,int r,int L,int R) {
// cout<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<tr[idx].mx1<<'\n';
if(L<=l&&r<=R) return tr[idx];
push_down(idx);
int mid=(l+r)>>1;
if(L<=mid&&R<=mid) return query(lc(idx),l,mid,L,R);
if(R>mid&&L>mid) return query(rc(idx),mid+1,r,L,R);
node x;
cg1(x,0,0,0); cg2(x,0,0,0,0); cg3(x,0);
x.len=r-l+1;
modi(x,query(lc(idx),l,mid,L,R),query(rc(idx),mid+1,r,L,R));
return x;
}
void update(int idx,int l,int r,int L,int R,int tag) {
// cout<<l<<' '<<r<<' '<<L<<' '<<R<<'\n';
if(L<=l&&r<=R) {
if(tag==1) {
int sz=tr[idx].len;
cg1(tr[idx],sz,sz,sz);
cg2(tr[idx],0,0,0,0);
cg3(tr[idx],1);
} else if(tag==2) {
int sz=tr[idx].len;
cg1(tr[idx],0,0,0);
cg2(tr[idx],sz,sz,sz,sz);
cg3(tr[idx],2);
} else {
node x=tr[idx];
if(x.tag==1) tr[idx].tag=2;
else if(x.tag==2) tr[idx].tag=1;
else if(x.tag==3) tr[idx].tag=0;
else tr[idx].tag=3;
cg1(tr[idx],x.l1,x.r1,x.mx1);
cg2(tr[idx],x.l0,x.r0,x.mx0,x.len-x.cnt1);
}
return ;
}
push_down(idx);
int mid=(l+r)>>1;
if(L<=mid) update(lc(idx),l,mid,L,R,tag);
if(R>mid) update(rc(idx),mid+1,r,L,R,tag);
push_up(idx);
}
//void check() {
// For(i,1,n) query_cnt(1,1,n,i,i);// puts("");
//}
signed main() {
// freopen("qwq.in","r",stdin);
// freopen("awa.out","w",stdout);
in2(n,m);
For(i,1,n) in1(a[i]);
build(1,1,n);
For(i,1,m) {
int opt,l,r;
in3(opt,l,r);
l++,r++;
if(opt==0) {
update(1,1,n,l,r,1);
} else if(opt==1) {
update(1,1,n,l,r,2);
} else if(opt==2) {
update(1,1,n,l,r,3);
} else if(opt==3) {
cout<<query_cnt(1,1,n,l,r)<<'\n';
} else cout<<query(1,1,n,l,r).mx1<<'\n';
// check();
}
}