5793__qwq @ 2023-07-17 21:43:50
#include<bits/stdc++.h>
#define N 100001<<2
using namespace std;
int n,m,f,x,y,a[N],s0[N],s1[N],l0[N],l1[N],r0[N],r1[N],bl0[N],bl1[N],re[N],eq0[N],eq1[N];
void print(int x,int l,int r){
cout<<l<<" "<<r<<':'<<s0[x]<<" "<<s1[x]<<" "<<l0[x]<<" "<<l1[x]<<" "<<r0[x]<<" "<<r1[x]<<" "<<bl0[x]<<" "<<bl1[x]<<'\n';
if(l==r)return;
int m=l+r>>1;
print(x<<1,l,m);
print(x<<1|1,m+1,r);
}
void get(int x,int a,int b,int c,int d,int e,int f,int g,int h){s0[x]=a;s1[x]=b;l0[x]=c;l1[x]=d;r0[x]=e;r1[x]=f;bl0[x]=g;bl1[x]=h;}
void pushup(int x){
s0[x]=s0[x<<1]+s0[x<<1|1];
s1[x]=s1[x<<1]+s1[x<<1|1];
if(l1[x<<1|1]==0)r0[x]=r0[x<<1|1]+r0[x<<1];else r0[x]=r0[x<<1|1];
if(r1[x<<1|1]==0)l0[x]=l0[x<<1|1]+l0[x<<1];else l0[x]=l0[x<<1|1];
if(l0[x<<1|1]==0)r1[x]=r1[x<<1|1]+r1[x<<1];else r1[x]=r1[x<<1|1];
if(r0[x<<1|1]==0)l1[x]=l1[x<<1|1]+l1[x<<1];else l1[x]=l1[x<<1|1];
bl0[x]=max(max(bl0[x<<1],bl0[x<<1|1]),r0[x<<1]+l0[x<<1|1]);
bl1[x]=max(max(bl1[x<<1],bl1[x<<1|1]),r1[x<<1]+l1[x<<1|1]);
}
void pushdown(int x,int l,int r){
int t=r-l+1;
if(eq0[x]){
eq0[x<<1]=eq0[x<<1|1]=1;
get(x<<1,t,0,t,0,t,0,t,0);
get(x<<1|1,t,0,t,0,t,0,t,0);
eq0[x]=0;
}
if(eq1[x]){
eq1[x<<1]=eq1[x<<1|1]=1;
get(x<<1,0,t,0,t,0,t,0,t);
get(x<<1|1,0,t,0,t,0,t,0,t);
eq1[x]=0;
}
if(re[x]){
re[x<<1]^=1;
re[x<<1|1]^=1;
swap(s0[x<<1],s1[x<<1]);swap(l0[x<<1],l1[x<<1]);
swap(r0[x<<1],r1[x<<1]);swap(bl0[x<<1],bl1[x<<1]);
swap(s0[x<<1|1],s1[x<<1|1]);swap(l0[x<<1|1],l1[x<<1|1]);
swap(r0[x<<1|1],r1[x<<1|1]);swap(bl0[x<<1|1],bl1[x<<1|1]);
re[x]=0;
}
}
void build(int x,int l,int r){
if(l==r){
int t=a[l];
get(x,1-t,t,1-t,t,1-t,t,1-t,t);
return;
}
int m=l+r>>1;
build(x<<1,l,m);
build(x<<1|1,m+1,r);
pushup(x);
}
void update(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
int t=r-l+1;
if(k==0){eq0[x]=1;get(x,t,0,t,0,t,0,t,0);}
if(k==1){eq1[x]=1;get(x,0,t,0,t,0,t,0,t);}
if(k==2){
re[x]^=1;
swap(s0[x],s1[x]);swap(l0[x],l1[x]);
swap(r0[x],r1[x]);swap(bl0[x],bl1[x]);
}
return ;
}
pushdown(x,l,r);
int m=l+r>>1;
if(L<=m)update(x<<1,l,m,L,R,k);
if(R>m)update(x<<1|1,m+1,r,L,R,k);
pushup(x);
}
int find1(int x,int l,int r,int L,int R){
if(L<=l&&r<=R)return s1[x];
pushdown(x,l,r);
int m=l+r>>1,ans=0;
if(L<=m)ans+=find1(x<<1,l,m,L,R);
if(R>m)ans+=find1(x<<1|1,m+1,r,L,R);
return ans;
}
int findb1(int x,int l,int r,int L,int R){
if(L<=l&&r<=R)return bl1[x];
pushdown(x,l,r);
int m=l+r>>1,ans=0;
if(L<=m)ans=max(ans,findb1(x<<1,l,m,L,R));
if(R>m)ans=max(ans,findb1(x<<1|1,m+1,r,L,R));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=n;++i){
print(1,1,n);
cin>>f>>x>>y;
++x,++y;
if(f<3)update(1,1,n,x,y,f);
else if(f==3) cout<<find1(1,1,n,x,y)<<'\n';
else cout<<findb1(1,1,n,x,y)<<'\n';
}
return 0;
}print是调试用的，用来输出整个树.
by 5793__qwq @ 2023-07-19 22:49:30
wc，要用struct。
by 5793__qwq @ 2023-07-19 22:50:35
#include<bits/stdc++.h>
#define N 100001<<2
#define debug cout<<x<<" "<<l<<" "<<r<<':'<<tree[x].s0<<" "<<tree[x].s1<<" "<<tree[x].l0<<" "<<tree[x].l1<<" "<<tree[x].r0<<" "<<tree[x].r1\
<<" "<<tree[x].bl0<<" "<<tree[x].bl1<<" "<<tree[x].len<<" tag:"<<tree[x].eq0<<" "<<tree[x].eq1<<" "<<tree[x].re<<'\n';
#define debug2 cout<<x.s0<<" "<<x.s1<<" "<<x.l0<<" "<<x.l1<<" "<<x.r0<<" "<<x.r1<<" "<<x.bl0<<" "<<x.bl1<<" "<<x.len<<" tag:"<<x.eq0<<" "<<x.eq1<<" "<<x.re<<'\n';
using namespace std;
int n,m,f,x,y,a[N];
struct node{
int s0,s1,l0,l1,r0,r1,bl0,bl1,len,re,eq0,eq1;
node(int s0=0,int s1=0,int l0=0,int l1=0,int r0=0,int r1=0,int bl0=0,int bl1=0,int len=0,int eq0=0,int eq1=0,int re=0):s0(s0),s1(s1),l0(l0),l1(l1),r0(r0),r1(r1),bl0(bl0),bl1(bl1),len(len),eq0(eq0),eq1(eq1),re(re){}
}tree[N];
void print(int x,int l,int r){
debug
if(l==r)return;
int m=l+r>>1;
print(x<<1,l,m);
print(x<<1|1,m+1,r);
}
void merge(node &o,node l,node r){
node x=node();
x.s0=l.s0+r.s0;
x.s1=l.s1+r.s1;
if(x.l1==0)x.r0=r.r0+l.r0;else x.r0=r.r0;
if(x.r1==0)x.l0=r.l0+l.l0;else x.l0=l.l0;
if(x.l0==0)x.r1=r.r1+l.r1;else x.r1=r.l1;
if(x.r0==0)x.l1=r.l1+l.l1;else x.l1=l.l1;
x.bl0=max(max(l.bl0,r.bl0),l.r0+r.l0);
x.bl1=max(max(l.bl1,r.bl1),l.r1+r.l1);
x.len=l.len+r.len;
o=x;
}
node go(node &x,int k){
if(k==0){x=node(x.len,0,x.len,0,x.len,0,x.len,0,x.len,1,x.eq1,x.re);}
if(k==1){x=node(0,x.len,0,x.len,0,x.len,0,x.len,x.len,x.eq0,1,x.re);}
if(k==2){x.re^=1;swap(x.s0,x.s1);swap(x.l0,x.l1);swap(x.r0,x.r1);swap(x.bl0,x.bl1);}
}
void pushdown(int x){
if(tree[x].eq0){
go(tree[x<<1],0);go(tree[x<<1|1],0);
tree[x].eq0=0;
}
if(tree[x].eq1){
go(tree[x<<1],1);go(tree[x<<1|1],1);
tree[x].eq1=0;
}
if(tree[x].re){
go(tree[x<<1],2);go(tree[x<<1|1],2);
tree[x].re=0;
}
}
void build(int x,int l,int r){
if(l==r){
int t=a[l];
if(a[l]==0)
tree[x]=node(1,0,1,0,1,0,1,0,1);else
tree[x]=node(0,1,0,1,0,1,0,1,1);
return;
}
int m=l+r>>1;
build(x<<1,l,m);
build(x<<1|1,m+1,r);
merge(tree[x],tree[x<<1],tree[x<<1|1]);
}
void update(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
go(tree[x],k);
return ;
}
pushdown(x);
int m=l+r>>1;
if(L<=m)update(x<<1,l,m,L,R,k);
if(R>m)update(x<<1|1,m+1,r,L,R,k);
merge(tree[x],tree[x<<1],tree[x<<1|1]);
}
int find1(int x,int l,int r,int L,int R){
if(L<=l&&r<=R)return tree[x].s1;
pushdown(x);
int m=l+r>>1,ans=0;
if(L<=m)ans+=find1(x<<1,l,m,L,R);
if(R>m)ans+=find1(x<<1|1,m+1,r,L,R);
return ans;
}
node findb1(int x,int l,int r,int L,int R){
if(r<L||R<l)return node();
if(L<=l&&r<=R)return tree[x];
pushdown(x);
int m=l+r>>1;
node ans=node();
merge(ans,findb1(x<<1,l,m,L,R),findb1(x<<1|1,m+1,r,L,R));
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=n;++i){
// print(1,1,n);
cin>>f>>x>>y;
++x,++y;
if(f<3)update(1,1,n,x,y,f);
else if(f==3) cout<<find1(1,1,n,x,y)<<'\n';
else cout<<findb1(1,1,n,x,y).bl1<<'\n';
}
return 0;
}by 5793__qwq @ 2023-07-19 22:51:08
过了样例与#11