为什么加了一句话就过了
查看原帖
为什么加了一句话就过了
1050021
likezheng2023楼主2024/7/18 17:56

为什么加了142行就过了
不加就不过

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	register int x=0,f=0;register char c=getchar();
	while(c<'0'||c>'9')f=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return f?-x:x;
}
const int MAXN=5e5;
int n,m,a[MAXN];
int la1[MAXN],an1[MAXN],ra1[MAXN],sum1[MAXN],la0[MAXN],ra0[MAXN],an0[MAXN],sum0[MAXN],ll[MAXN],rr[MAXN];
int fuz[MAXN],re[MAXN];
void pushup(int now){
	int ls=now*2,rs=now*2+1;
	ll[now]=ll[ls];rr[now]=rr[rs];
	
	sum1[now]=sum1[ls]+sum1[rs];//sum0/1
	sum0[now]=sum0[ls]+sum0[rs];
	
	if(sum1[ls]==rr[ls]-ll[ls]+1)la1[now]=sum1[ls]+la1[rs];//la0/1
	else la1[now]=la1[ls];
	if(sum0[ls]==rr[ls]-ll[ls]+1)la0[now]=sum0[ls]+la0[rs];
	else la0[now]=la0[ls];
	
	if(sum1[rs]==rr[rs]-ll[rs]+1)ra1[now]=sum1[rs]+ra1[ls];//ra0/1
	else ra1[now]=ra1[rs];
	if(sum0[rs]==rr[rs]-ll[rs]+1)ra0[now]=sum0[rs]+ra0[ls];
	else ra0[now]=ra0[rs];
	
	an1[now]=max({an1[ls],an1[rs],ra1[ls]+la1[rs]});//an0/1
	an0[now]=max({an0[ls],an0[rs],ra0[ls]+la0[rs]});
	
}

void pushdown(int now){
	int ls=now*2,rs=now*2+1;
	if(fuz[now]!=-1){
		fuz[ls]=fuz[rs]=fuz[now];
		re[ls]=re[rs]=0;
		la1[ls]=ra1[ls]=an1[ls]=sum1[ls]=(fuz[now]==1)*(rr[ls]-ll[ls]+1);
		la1[rs]=ra1[rs]=an1[rs]=sum1[rs]=(fuz[now]==1)*(rr[rs]-ll[rs]+1);
		la0[ls]=ra0[ls]=an0[ls]=sum0[ls]=(fuz[now]==0)*(rr[ls]-ll[ls]+1);
		la0[rs]=ra0[rs]=an0[rs]=sum0[rs]=(fuz[now]==0)*(rr[rs]-ll[rs]+1);
		fuz[now]=-1;
	}
	if(re[now]){
		if(fuz[ls]!=-1)fuz[ls]^=1;
		if(fuz[rs]!=-1)fuz[rs]^=1;
		re[ls]^=1;
		re[rs]^=1;
		swap(la1[ls],la0[ls]);swap(ra1[ls],ra0[ls]);swap(sum1[ls],sum0[ls]);swap(an1[ls],an0[ls]);
		swap(la1[rs],la0[rs]);swap(ra1[rs],ra0[rs]);swap(sum1[rs],sum0[rs]);swap(an1[rs],an0[rs]);
		re[now]=0;
	}
}
void build(int cl=1,int cr=n,int p=1){
	fuz[p]=-1;re[p]=0;
	if(cl==cr){
		ll[p]=rr[p]=cl;
		la1[p]=an1[p]=ra1[p]=sum1[p]=(a[cl]==1);
		la0[p]=an0[p]=ra0[p]=sum0[p]=(a[cl]==0);
		return;
	}
	int mid=(cl+cr)>>1;
	build(cl,mid,p*2),build(mid+1,cr,p*2+1);
	pushup(p);
}
void fuzhi(int l,int r,int x,int cl=1,int cr=n,int p=1){
	if(cr<l||cl>r||cl>cr)return;
	if(l<=cl&&cr<=r){
		fuz[p]=x;re[p]=0;
		la1[p]=ra1[p]=sum1[p]=an1[p]=(x==1)*(cr-cl+1);
		la0[p]=ra0[p]=sum0[p]=an0[p]=(x==0)*(cr-cl+1);
		return;
	}
	int mid=(cl+cr)>>1;
	pushdown(p);
	fuzhi(l,r,x,cl,mid,p*2);fuzhi(l,r,x,mid+1,cr,p*2+1);
	pushup(p);
}
void fanzhuan(int l,int r,int cl=1,int cr=n,int p=1){
	if(cr<l||cl>r||cl>cr)return;
	if(l<=cl&&cr<=r){
		re[p]^=1;
		if(fuz[p]!=-1)fuz[p]^=1;
		swap(la1[p],la0[p]);swap(ra1[p],ra0[p]);swap(an1[p],an0[p]);swap(sum1[p],sum0[p]);
		return;
	}
	int mid=(cl+cr)>>1;
	pushdown(p);
	fanzhuan(l,r,cl,mid,p*2);fanzhuan(l,r,mid+1,cr,p*2+1);
	pushup(p);
}
int que1(int l,int r,int cl=1,int cr=n,int p=1){
	if(cr<l||cl>r||cl>cr)return 0;
	if(l<=cl&&cr<=r)return sum1[p];
	int mid=(cl+cr)>>1;
	pushdown(p);
	return que1(l,r,cl,mid,p*2)+que1(l,r,mid+1,cr,p*2+1);
}
struct node{
	int la1,la0,ra1,ra0,an1,an0,sum1,sum0,rr,ll;
}t;
node hb(node x,node y){
	
	node res;
	res.rr=y.rr;res.ll=x.ll;
	res.sum1=x.sum1+y.sum1;//sum0/1
	res.sum0=x.sum0+y.sum0;
	
	if(x.sum1==x.rr-x.ll+1)res.la1=x.sum1+y.la1;//la0/1
	else res.la1=x.la1;
	if(x.sum0==x.rr-x.ll+1)res.la0=x.sum0+y.la0;
	else res.la0=x.la0;
	
	if(y.sum1==y.rr-y.ll+1)res.ra1=y.sum1+x.ra1;//ra0/1
	else res.ra1=y.ra1;
	if(y.sum0==y.rr-y.ll+1)res.ra0=y.sum0+x.ra0;
	else res.ra0=y.ra0;
	
	res.an1=max({x.an1,y.an1,x.ra1+y.la1});//an0/1
	res.an0=max({x.an0,y.an0,x.ra0+y.la0});
	return res;
}
node que2(int l,int r,int cl=1,int cr=n,int p=1){
	if(cr<l||cl>r||cl>cr)return {0,0,0,0,0,0,0,0};
	if(l<=cl&&cr<=r)return {la1[p],la0[p],ra1[p],ra0[p],an1[p],an0[p],sum1[p],sum0[p],cr,cl};
	int mid=(cl+cr)>>1;
	pushdown(p);
	return hb(que2(l,r,cl,mid,p*2),que2(l,r,mid+1,cr,p*2+1));
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build();
	for(int i=1;i<=m;i++){
		int op=read(),l=read(),r=read();
		l++,r++;
		if(op==0||op==1){
			fuzhi(l,r,op);
//			for(int j=1;j<=n;j++)que1(j,j);
		}
		else if(op==2){
			fanzhuan(l,r);
		}
		else if(op==3){
			cout<<que1(l,r)<<'\n';
		}
		else{
			cout<<que2(l,r).an1<<'\n';
		}
	}

	return 0;
}

2024/7/18 17:56
加载中...