和前面差不多的区间合并,只不多操作多一些,要同时记录1和0的情况
#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e5;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b;b^=a;a^=b;return;}
int sum[maxn<<2],lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int zmmax[maxn<<2],zlmax[maxn<<2],zrmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2],rev[maxn<<2];
void do_set(int id,int l,int r)
{
sum[id]=lmax[id]=rmax[id]=mmax[id]=r-l+1;
zmmax[id]=zlmax[id]=zrmax[id]=0;
set[id]=1;reset[id]=rev[id]=0;
return;
}
void do_reset(int id,int l,int r)
{
sum[id]=lmax[id]=rmax[id]=mmax[id]=0;
zmmax[id]=zlmax[id]=zrmax[id]=r-l+1;
reset[id]=1;set[id]=rev[id]=0;
}
void do_rev(int id,int l,int r)
{
if(set[id]) {do_reset(id,l,r);return;}
if(reset[id]) {do_set(id,l,r);return;}
rev[id]^=1;
sum[id]=r-l+1-sum[id];
swap(mmax[id],zmmax[id]);
swap(lmax[id],zlmax[id]);
swap(rmax[id],zrmax[id]);
return;
}
void opt(int id,int l,int r,int type)
{
if(type==0) do_reset(id,l,r);
if(type==1) do_set(id,l,r);
if(type==2) do_rev(id,l,r);
return;
}
void pushup(int id,int l,int r)
{
int m=(l+r)/2;
int lenl=m-l+1,lenr=r-m;
sum[id]=sum[lson]+sum[rson];
mmax[id]=max(mmax[lson],mmax[rson]);
mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
lmax[id]=lmax[lson];
rmax[id]=rmax[rson];
if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
zmmax[id]=max(zmmax[lson],zmmax[rson]);
zmmax[id]=max(zmmax[id],zrmax[lson]+zlmax[rson]);
zlmax[id]=zlmax[lson];
zrmax[id]=zrmax[rson];
if(zlmax[lson]==lenl) zlmax[id]+=zlmax[rson];
if(zrmax[rson]==lenr) zrmax[id]+=zrmax[lson];
return;
}
void pushdown(int id,int l,int r)
{
int m=(l+r)/2;
if(set[id]){do_set(lson,l,m);do_set(rson,m+1,r);set[id]=0;}
if(reset[id]){do_reset(lson,l,m);do_reset(rson,m+1,r);reset[id]=0;}
if(rev[id]){do_rev(lson,l,m);do_rev(rson,m+1,r);rev[id]=0;}
return;
}
void build(int id,int l,int r)
{
set[id]=reset[id]=rev[id]=0;
if(l==r)
{
scanf("%d",&sum[id]);
lmax[id]=rmax[id]=mmax[id]=sum[id];
zmmax[id]=zlmax[id]=zrmax[id]=1-sum[id];
return;
}
int m=(l+r)/2;
build(lson,l,m);
build(rson,m+1,r);
pushup(id,l,r);
return;
}
void update(int id,int l,int r,int L,int R,int type)
{
if(L<=l && r<=R)
{
opt(id,l,r,type);
return;
}
pushdown(id,l,r);
int m=(l+r)/2;
if(L<=m) update(lson,l,m,L,R,type);
if(R>m) update(rson,m+1,r,L,R,type);
pushup(id,l,r);
return;
}
int query_sum(int id,int l,int r,int L,int R)
{
if(L<=l && r<=R) return sum[id];
pushdown(id,l,r);
int m=(l+r)/2,ret=0;
if(L<=m) ret+=query_sum(lson,l,m,L,R);
if(R>m) ret+=query_sum(rson,m+1,r,L,R);
return ret;
}
int query_len(int id,int l,int r,int L,int R)
{
if(L<=l && r<=R) return mmax[id];
pushdown(id,l,r);
int m=(l+r)/2,ret=0;
if(L<=m) ret=max(ret,query_len(lson,l,m,L,R));
if(R>m) ret=max(ret,query_len(rson,m+1,r,L,R));
ret=max(ret,min(R,m+lmax[rson])-max(L,m+1-rmax[lson])+1);
return ret;
}
int main()
{
int i,j,t;
int n,m;
int op,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&a,&b);a++;b++;
if(op<=2) update(1,1,n,a,b,op);
if(op==3) printf("%d\n",query_sum(1,1,n,a,b));
if(op==4) printf("%d\n",query_len(1,1,n,a,b));
}
}
return 0;
}