Kissky @ 2023-01-19 19:55:29
AC（1，2，3，11） WA（4，5，6，7，8，9，10）
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define dd double
#define re register
#define il inline
#define lb(x) ((x)&(-x))
#define pb push_back
#define pa pair
#define fr frist
#define sc second
#define rep(i,a,n) for(register int i=a;i<=n;i++)
#define fep(i,a,n) for(register int i=n;i>=a;i--)
using namespace std;
template <class T> void read(T &x){
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;return ;
}
bool cmp(int x,int y){return x>y;}
dd ddabs(double x){if(x<0) return -x;else return x;}
int gcd(int a, int b){return b ? gcd(b,a%b):a;}
int max(int a,int b){if(a>b) return a;else return b;}
int min(int a,int b){if(a<b) return a;else return b;}
int qkpow(int x,int y){int ans=1;while(y){if(y&1) ans*=x;y>>=1;x*=x;}return ans;}
const double eps=1e-6;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int n,m;
int a[maxn];
struct note
{
int l,r,val,len,la1,la2,la3;
int qc1,lc1,rc1;
int qc0,lc0,rc0;
// l是区间左侧，r是区间右侧 val是区间中1的个数，len是区间长度
// la1取反用的,la2全都变成0,la3全部变成1
// qc1表示区间中最长连续1的个数。
// lc1表示区间中以左端点为起点从左往右连续1的个数
// rc1表示区间中以右端点为终点从左往右连续1的个数
// qc1表示区间中最长连续0的个数。
// lc0表示区间中以左端点为起点从左往右连续0的个数
// rc0表示区间中以右端点为终点从左往右连续0的个数
}t[maxn*4];
void pup(int p)
{
if(t[p<<1].lc1==t[p<<1].len)
t[p].lc1=t[p<<1].len+t[p<<1|1].lc1;
else
t[p].lc1=t[p<<1].lc1;
if(t[p<<1|1].rc1==t[p<<1|1].len)
t[p].rc1=t[p<<1|1].len+t[p<<1].rc1;
else
t[p].rc1=t[p<<1|1].rc1;
t[p].qc1=max(max(t[p<<1].qc1,t[p<<1|1].qc1),t[p<<1].rc1+t[p<<1|1].lc1);
if(t[p<<1].lc0==t[p<<1].len)
t[p].lc0=t[p<<1].len+t[p<<1|1].lc0;
else
t[p].lc0=t[p<<1].lc0;
if(t[p<<1|1].rc0==t[p<<1|1].len)
t[p].rc0=t[p<<1|1].len+t[p<<1].rc0;
else
t[p].rc0=t[p<<1|1].rc0;
t[p].qc0=max(max(t[p<<1].qc0,t[p<<1|1].qc0),t[p<<1].rc0+t[p<<1|1].lc0);
t[p].val=t[p<<1].val+t[p<<1|1].val;
}
void build(int p,int l,int r)//建树
{
t[p].l=l;t[p].r=r;
t[p].len=r-l+1;
if(l==r)
{
t[p].val=a[l];
t[p].lc1=t[p].rc1=t[p].qc1=a[l];
t[p].lc0=t[p].rc0=t[p].qc0=1^a[l];
return ;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pup(p);
}
void spread(int p)// 懒标记传递
{
if(t[p].la2)//变为0
{
t[p<<1].la2=1;
t[p<<1].la1=0;
t[p<<1].qc0=t[p<<1].lc0=t[p<<1].rc0=t[p<<1].len;
t[p<<1].val=t[p<<1].qc1=t[p<<1].lc1=t[p<<1].rc1=0;
t[p<<1|1].la2=1;
t[p<<1|1].la1=0;
t[p<<1|1].qc0=t[p<<1|1].lc0=t[p<<1|1].rc0=t[p<<1|1].len;
t[p<<1|1].val=t[p<<1|1].qc1=t[p<<1|1].lc1=t[p<<1|1].rc1=0;
t[p].la2=0;
t[p].la1=0;
}
if(t[p].la3)
{
t[p<<1].la3=1;
t[p<<1].la1=0;
t[p<<1].qc0=t[p<<1].lc0=t[p<<1].rc0=0;
t[p<<1].val=t[p<<1].qc1=t[p<<1].lc1=t[p<<1].rc1=t[p<<1].len;
t[p<<1|1].la3=1;
t[p<<1|1].la1=0;
t[p<<1|1].qc0=t[p<<1|1].lc0=t[p<<1|1].rc0=0;
t[p<<1|1].val=t[p<<1|1].qc1=t[p<<1|1].lc1=t[p<<1|1].rc1=t[p<<1|1].len;
t[p].la3=0;
t[p].la1=0;
}
if(t[p].la1)// 全部取反.
{
t[p<<1].val=t[p<<1].len-t[p<<1].val;
swap(t[p<<1].qc1,t[p<<1].qc0);
swap(t[p<<1].lc1,t[p<<1].lc0);
swap(t[p<<1].rc1,t[p<<1].rc0);
if(t[p<<1].la2) t[p<<1].la2=0,t[p<<1].la3=1;
else if(t[p<<1].la3) t[p<<1].la3=0,t[p<<1].la2=1;
else t[p<<1].la1^=1;
t[p<<1|1].val=t[p<<1|1].len-t[p<<1|1].val;
swap(t[p<<1|1].qc1,t[p<<1|1].qc0);
swap(t[p<<1|1].lc1,t[p<<1|1].lc0);
swap(t[p<<1|1].rc1,t[p<<1|1].rc0);
if(t[p<<1|1].la2) t[p<<1|1].la2=0,t[p<<1|1].la3=1;
else if(t[p<<1|1].la3) t[p<<1|1].la3=0,t[p<<1|1].la2=1;
else t[p<<1|1].la1^=1;
t[p].la1=0;
}
}
void change1(int p,int l,int r)//全部取反
{
if(t[p].l>=l&&t[p].r<=r)
{
t[p].val=t[p].len-t[p].val;
swap(t[p].qc1,t[p].qc0);
swap(t[p].lc1,t[p].lc0);
swap(t[p].rc1,t[p].rc0);
t[p].la1^=1;
return ;
}
spread(p);
int mid=t[p].r+t[p].l>>1;
if(l<=mid) change1(p<<1,l,r);
if(r> mid) change1(p<<1|1,l,r);
pup(p);
}
void change2(int p,int l,int r)// 全部变成0
{
if(t[p].l>=l&&t[p].r<=r)
{
t[p].qc0=t[p].lc0=t[p].rc0=t[p].len;
t[p].val=t[p].qc1=t[p].lc1=t[p].rc1=0;
t[p].la2=1;
t[p].la1=0;
return ;
}
spread(p);
int mid=t[p].r+t[p].l>>1;
if(l<=mid) change2(p<<1,l,r);
if(r> mid) change2(p<<1|1,l,r);
pup(p);
}
void change3(int p,int l,int r)// 全部变成1
{
if(t[p].l>=l&&t[p].r<=r)
{
t[p].qc0=t[p].lc0=t[p].rc0=0;
t[p].val=t[p].qc1=t[p].lc1=t[p].rc1=t[p].len;
t[p].la3=1;
t[p].la1=0;
return ;
}
spread(p);
int mid=t[p].r+t[p].l>>1;
if(l<=mid) change3(p<<1,l,r);
if(r> mid) change3(p<<1|1,l,r);
pup(p);
}
int ask1(int p,int l,int r)//询问区间有多少个1
{
spread(p);
if(t[p].l>=l&&t[p].r<=r) return t[p].val;
int mid=t[p].l+t[p].r>>1,ans=0;
if(l<=mid) ans+=ask1(p<<1,l,r);
if(r> mid) ans+=ask1(p<<1|1,l,r);
return ans;
}
note ask2(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p];
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid&&mid<r)
{
note lans,rans,ans;
lans=ask2(p<<1,l,r);
rans=ask2(p<<1|1,l,r);
ans.lc1=lans.lc1;
if(lans.lc1==t[p<<1].len) ans.lc1+=rans.lc1;
ans.rc1=rans.rc1;
if(rans.rc1==t[p<<1|1].len)ans.rc1+=lans.rc1;
ans.qc1=max(lans.rc1+rans.lc1,max(lans.qc1,rans.qc1));
return ans;
}
if(l<=mid)return ask2(p<<1,l,r);
if(r>mid)return ask2(p<<1|1,l,r);
}
signed main()
{
read(n);read(m);
rep(i,1,n) read(a[i]);
build(1,1,n);
rep(i,1,m)
{
int opt,l,r;
read(opt);read(l);read(r);l++,r++;
switch(opt)
{
case(0):
{
change2(1,l,r);
break;
}
case(1):
{
change3(1,l,r);
break;
}
case(2):
{
change1(1,l,r);
break;
}
case(3):
{
// cout<<"Ans==";
cout<<ask1(1,l,r)<<"\n";
break;
}
case(4):
{
// cout<<"Ans==";
cout<<ask2(1,l,r).qc1<<"\n";
break;
}
}
/* cout<<"i=="<<i<<"\n";
for(int j=1;j<=n;j++)
cout<<"a=="<<ask1(1,j,j)<<"\n";
cout<<"**********************\n";*/
}
return 0;
}