LordLaffey @ 2021-07-06 16:37:47
#include<iostream>
#include<cstdio>
using namespace std;
const int SIZE=1e5;
int ls(int i){return i<<1;}
int rs(int i){return i<<1|1;}
int _max(int x,int y){return x>y?x:y;}
void _swap(int &x,int &y){int c=x;x=y,y=c;}
int input[SIZE+10];
struct node{
int l,r;
int sum_0,sum_1,l_0,l_1,r_0,r_1,all_0,all_1;
int lz_qf,lz_fz;
}tree[SIZE*4+10];
int len(int i){return tree[i].r-tree[i].l+1;}
//void up(node tl,node tr,node& tmp){
//
// tmp.all_0=_max(tl.all_0,_max(tr.all_0,tl.r_0+tr.l_0));
// tmp.all_1=_max(tl.all_1,_max(tr.all_1,tl.r_1+tr.l_1));
//
//}
node update(node tl,node tr){
node tmp;
tmp.l=tl.l,tmp.r=tr.r;
tmp.lz_qf=0,tmp.lz_fz=-1;
tmp.sum_0=tl.sum_0+tr.sum_0;
tmp.sum_1=tl.sum_1+tr.sum_1;
tmp.l_0=tl.l_0;tmp.r_0=tr.r_0;
tmp.l_1=tl.l_1;tmp.r_1=tr.r_1;
if((tl.r-tl.l+1)==tl.sum_1) tmp.l_1+=tr.l_1;
if((tr.r-tr.l+1)==tr.sum_1) tmp.r_1+=tl.r_1;
if((tl.r-tl.l+1)==tl.sum_0) tmp.l_0+=tr.l_0;
if((tl.r-tl.l+1)==tr.sum_0) tmp.r_0+=tl.r_0;
// up(tl,tr,tmp);
tmp.all_0=_max(tl.all_0,_max(tr.all_0,tl.r_0+tr.l_0));
tmp.all_1=_max(tl.all_1,_max(tr.all_1,tl.r_1+tr.l_1));
return tmp;
}
void fz0(int i){
tree[i].sum_0=tree[i].l_0=tree[i].r_0=tree[i].all_0=tree[i].r-tree[i].l+1,
tree[i].sum_1=tree[i].l_1=tree[i].r_1=tree[i].all_1=0;
}
void fz1(int i){
tree[i].sum_1=tree[i].l_1=tree[i].r_1=tree[i].all_1=tree[i].r-tree[i].l+1,
tree[i].sum_0=tree[i].l_0=tree[i].r_0=tree[i].all_0=0;
}
void qf(int i){
_swap(tree[i].sum_1,tree[i].sum_0),
_swap(tree[i].l_1,tree[i].l_0),
_swap(tree[i].r_1,tree[i].r_0),
_swap(tree[i].all_1,tree[i].all_0);
}
void lztage(int i){
if(tree[i].lz_fz==0) fz0(ls(i)),fz0(rs(i));
if(tree[i].lz_fz==1) fz1(ls(i)),fz1(rs(i));
if(tree[i].lz_qf) qf(ls(i)),qf(rs(i));
if(tree[i].lz_fz!=-1)
tree[ls(i)].lz_qf=tree[rs(i)].lz_qf=0,tree[ls(i)].lz_fz=tree[rs(i)].lz_fz=tree[i].lz_fz;
// if(tree[ls(i)].lz_fz!=-1&&tree[i].lz_qf) tree[ls(i)].lz_fz=1-tree[ls(i)].lz_fz;
// if(tree[rs(i)].lz_fz!=-1&&tree[i].lz_qf) tree[rs(i)].lz_fz=1-tree[rs(i)].lz_fz;
if(tree[i].lz_qf) tree[ls(i)].lz_qf^=1,tree[rs(i)].lz_qf^=1;
tree[i].lz_fz=-1,tree[i].lz_qf=0;
}
void build(int l,int r,int i){
tree[i].l=l,tree[i].r=r,tree[i].lz_qf=0,tree[i].lz_fz=-1;
if(l==r)
{
tree[i].sum_0=tree[i].l_0=tree[i].r_0=tree[i].all_0=!input[l];
tree[i].sum_1=tree[i].l_1=tree[i].r_1=tree[i].all_1=input[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls(i));
build(mid+1,r,rs(i));
tree[i]=update(tree[ls(i)],tree[rs(i)]);
}
void change(int l,int r,int i,int opt){
if(tree[i].l>=l&&tree[i].r<=r)
{
if(opt==0)
{
fz0(i);
tree[i].lz_qf=0,tree[i].lz_fz=opt;
}
if(opt==1)
{
fz1(i);
tree[i].lz_qf=0,tree[i].lz_fz=opt;
}
if(opt==2)
{
qf(i);
tree[i].lz_qf^=1;
}
return ;
}
lztage(i);
if(tree[ls(i)].r>=l) change(l,r,ls(i),opt);
if(tree[rs(i)].l<=r) change(l,r,rs(i),opt);
tree[i]=update(tree[ls(i)],tree[rs(i)]);
}
int search1(int l,int r,int i){
if(tree[i].l>=l&&tree[i].r<=r) return tree[i].sum_1;
lztage(i);
int sum=0;
if(tree[ls(i)].r>=l) sum+=search1(l,r,ls(i));
if(tree[rs(i)].l<=r) sum+=search1(l,r,rs(i));
return sum;
}
node search2(int l,int r,int i){
if(tree[i].l>=l&&tree[i].r<=r) return tree[i];
lztage(i);
if(tree[ls(i)].r>=r) return search2(l,r,ls(i));
if(tree[rs(i)].l<=l) return search2(l,r,rs(i));
else
{
node tl=search2(l,r,ls(i)),tr=search2(l,r,rs(i));
return update(tl,tr);
}
}
int search3(int i,int s){
if(tree[i].l==tree[i].r) return tree[i].sum_1;
lztage(i);
if(tree[ls(i)].r>=s) return search3(ls(i),s);
if(tree[rs(i)].l<=s) return search3(rs(i),s);
}//debug
void debug(int n){
printf("\n***********************\n");
for(int i=1;i<=n;i++)
printf("%d ",search3(1,i));
printf("\n***********************\n");
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&input[i]);
build(1,n,1);
while(m--)
{
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
l++,r++;
if(r>n) r=n;
if(opt<=2) change(l,r,1,opt);
else
{
if(opt==3) printf("%d\n",search1(l,r,1));
if(opt==4) printf("%d\n",search2(l,r,1).all_1);
}
}
return 0;
}白天稳定在线