一只退役蒟蒻 @ 2020-08-10 14:20:44
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int n,m;
bool a[100005];int id[100005],K;
int L[405],R[405];
int ls[405],rs[405],sum[405],maxx[405];//1的系列
int LS[405],RS[405],MAXX[405],SUM[405];//0的系列
int rev[405],bj[405];//翻转标记,覆盖标记
void pushdown(int x)
{
int ll=L[x],rr=R[x];
if(~bj[x])
{
for(int i=ll;i<=rr;++i)a[i]=bj[x];
bj[x]=-1;rev[x]=0;
}
else if(rev[x])
{
for(int i=ll;i<=rr;++i)a[i]^=1;
rev[x]=0;
}
}
void Get(int x)
{
int ll=L[x],rr=R[x],tmp,tot;maxx[x]=MAXX[x]=0;
tmp=0;for(int i=ll;i<=rr;++i)if(a[i])++tmp;else break;ls[x]=tmp;
tmp=0;for(int i=rr;i>=ll;--i)if(a[i])++tmp;else break;rs[x]=tmp;
tmp=0;for(int i=ll;i<=rr;++i)if(!a[i])++tmp;else break;LS[x]=tmp;
tmp=0;for(int i=rr;i>=ll;--i)if(!a[i])++tmp;else break;RS[x]=tmp;
tmp=0;tot=0;
for(int i=ll;i<=rr;++i)if(a[i]==1){++tmp;++tot;}else {maxx[x]=max(maxx[x],tmp);tmp=0;}
sum[x]=tot;maxx[x]=max(maxx[x],tmp);
tmp=0;tot=0;
for(int i=ll;i<=rr;++i)if(!a[i]){++tmp;++tot;}else {MAXX[x]=max(MAXX[x],tmp);tmp=0;}
SUM[x]=tot;MAXX[x]=max(MAXX[x],tmp);
}
void Sol(int l,int r,int bj)
{
if(bj^2)for(int i=l;i<=r;++i)a[i]=bj;
else for(int i=l;i<=r;++i)a[i]^=1;
Get(id[l]);
}
void Change(int num,int l,int r)
{
int idl=id[l],idr=id[r];
pushdown(idl);pushdown(idr);
if(idl==idr){Sol(l,r,num);return;}
Sol(l,R[idl],num);Sol(L[idr],r,num);
for(int i=idl+1;i<=idr-1;++i)
{
ls[i]=rs[i]=maxx[i]=sum[i]=num?R[i]-L[i]+1:0;
LS[i]=RS[i]=MAXX[i]=SUM[i]=num?0:R[i]-L[i]+1;
rev[i]=0;bj[i]=num;
}
}
void Sol_rev(int l,int r)
{
int idl=id[l],idr=id[r];
pushdown(idl);pushdown(idr);
if(idl==idr){Sol(l,r,2);return;}
Sol(l,R[idl],2);Sol(L[idr],r,2);
for(int i=idl+1;i<=idr-1;++i)
{
if(~bj[i])bj[i]^=1;//前面已经覆盖为某个值,整体取反
else rev[i]^=1;
swap(ls[i],LS[i]);swap(rs[i],RS[i]);swap(sum[i],SUM[i]);swap(maxx[i],MAXX[i]);
}
}
int Ask_sum(int l,int r)
{
int idl=id[l],idr=id[r],ans=0;
pushdown(idl);pushdown(idr);
if(idl==idr){for(int i=l;i<=r;++i)if(a[i])++ans;return ans;}
for(int i=l;i<=R[idl];++i)if(a[i])++ans;
for(int i=L[idr];i<=r;++i)if(a[i])++ans;
for(int i=idl+1;i<=idr-1;++i)ans+=sum[i];
return ans;
}
int Ask_len(int l,int r)
{
int idl=id[l],idr=id[r],cnt=0,Maxx=0;
int lst=0;
pushdown(idl);pushdown(idr);
if(idl==idr){for(int i=l;i<=r;++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}return max(Maxx,cnt);}
for(int i=R[idl];i>=l;--i)if(a[i])++lst;else break;
for(int i=idl+1;i<=idr-1;++i)
{
lst+=ls[i];
Maxx=max(Maxx,lst);
if(maxx[i]^(R[i]-L[i]+1))lst=0;
if(!lst)lst=rs[i];
Maxx=max(Maxx,ls[i]);
}
for(int i=l;i<=R[idl];++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}
Maxx=max(Maxx,cnt);cnt=0;
for(int i=L[idr];i<=r;++i)if(a[i])++cnt;else {Maxx=max(Maxx,cnt);cnt=0;}
Maxx=max(Maxx,cnt);cnt=0;
for(int i=L[idr];i<=r;++i)if(a[i])++cnt;else break;
return max(Maxx,lst+cnt);
}
int main()
{
// freopen("9.in","r",stdin);
// freopen("99.out","w",stdout);
n=read();m=read();K=sqrt(n);
for(int i=1;i<=n;++i){a[i]=read();id[i]=(i-1)/K+1;}
for(int i=1;i<=id[n];++i)bj[i]=-1;
for(int i=1;i<=id[n];++i){L[i]=(i-1)*K+1;R[i]=min(i*K,n);Get(i);}
// for(int i=1;i<=id[n];++i)cout<<ls[i]<<" "<<rs[i]<<" "<<sum[i]<<" "<<maxx[i]<<" "<<LS[i]<<" "<<RS[i]<<" "<<SUM[i]<<" "<<MAXX[i]<<endl;
int opt,l,r;
for(int i=1;i<=m;++i)
{
opt=read();l=read()+1;r=read()+1;
if(!opt)Change(0,l,r);
else if(opt==1)Change(1,l,r);
else if(opt==2)Sol_rev(l,r);
else if(opt==3)print(Ask_sum(l,r),'\n');
else print(Ask_len(l,r),'\n');
// for(int j=1;j<=id[n];++j)pushdown(j);
// for(int i=1;i<=n;++i)cout<<a[i]<<" ";cout<<endl;
}
return 0;
}
by 一只退役蒟蒻 @ 2020-08-10 14:21:47
大概是4操作锅了,有的4操作莫名输出0QAQ
by NXYorz @ 2020-08-10 14:22:50
qwq
by 一只退役蒟蒻 @ 2020-08-10 14:23:24
@NXYorz 线段树pushdown/pushup太毒瘤了,写的分块qwq
by wbt0910 @ 2021-08-26 10:49:26
1202年调0202年自己的代码祭QAQ