提交记录

和代码，思路是第一篇题解，

• sum 记录区间内 1 的个数
• len 记录区间长度
• tag 懒标记
• lmax 以最左边为端点的连续 0 的个数
• rmax 以最右边为端点的连续 0 的个数
• ans 区间内最长的连续 0 的个数

#include<iostream>
using namespace std;
int n,m;
struct node{int sum,len,tag,lmax,rmax,ans;}tree[800015];
void build(int x,int l,int r){
	tree[x].sum=tree[x].len=r-l+1;//因为初始时无脑洞(0)，简单建一下即可 
	if(l==r)return;
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void pushdown(int x){
	if(tree[x].tag==1){//1->0 
		tree[x<<1].tag=tree[x<<1|1].tag=1;
		tree[x<<1].sum=0;
		tree[x<<1|1].sum=0;
		tree[x<<1].lmax=tree[x<<1].rmax=tree[x<<1].ans=tree[x<<1].len;
		tree[x<<1|1].lmax=tree[x<<1|1].rmax=tree[x<<1|1].ans=tree[x<<1|1].len;
		tree[x].tag=0;
		return;
	}
	if(tree[x].tag==2){//0->1 
		tree[x<<1].tag=tree[x<<1|1].tag=2;
		tree[x<<1].sum=tree[x<<1].len;
		tree[x<<1|1].sum=tree[x<<1|1].len;
		tree[x<<1].lmax=tree[x<<1].rmax=tree[x<<1].ans=0;
		tree[x<<1|1].lmax=tree[x<<1|1].rmax=tree[x<<1|1].ans=0;
		tree[x].tag=0;
		return;
	}
}
void add(int x,int l,int r,int al,int ar){//0->1 
	if(l>ar||r<al)return;
	if(l>=al&&r<=ar){
		tree[x].tag=2;
		tree[x].sum=tree[x].len;
		tree[x].lmax=tree[x].rmax=tree[x].ans=0;
		return;
	}
	if(tree[x].tag)pushdown(x);//下传 
	int mid=l+r>>1;
	add(x<<1,l,mid,al,ar);
	add(x<<1|1,mid+1,r,al,ar);
	//pushup散装 
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
	tree[x].lmax=tree[x<<1].lmax;
	if(tree[x<<1].lmax==tree[x<<1].len)tree[x].lmax+=tree[x<<1|1].lmax;
	tree[x].rmax=tree[x<<1|1].rmax;
	if(tree[x<<1|1].rmax==tree[x<<1|1].len)tree[x].rmax+=tree[x<<1].rmax;
	tree[x].ans=max(tree[x<<1].rmax+tree[x<<1|1].lmax,max(tree[x<<1].ans,tree[x<<1|1].ans));
}
void del(int x,int l,int r,int al,int ar){//1->0 
	if(l>ar||r<al)return;
	if(l>=al&&r<=ar){
		tree[x].tag=1;
		tree[x].sum=0;
		tree[x].lmax=tree[x].rmax=tree[x].ans=tree[x].len;
		return;
	}
	if(tree[x].tag)pushdown(x);//下传 
	int mid=l+r>>1;
	del(x<<1,l,mid,al,ar);
	del(x<<1|1,mid+1,r,al,ar);
	//pushup散装 
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
	tree[x].lmax=tree[x<<1].lmax;
	if(tree[x<<1].lmax==tree[x<<1].len)tree[x].lmax+=tree[x<<1|1].lmax;
	tree[x].rmax=tree[x<<1|1].rmax;
	if(tree[x<<1|1].rmax==tree[x<<1|1].len)tree[x].rmax+=tree[x<<1].rmax;
	tree[x].ans=max(tree[x<<1].rmax+tree[x<<1|1].lmax,max(tree[x<<1].ans,tree[x<<1|1].ans));
}
node emp={0,0,0,0,0,0};//空儿子 
node ask(int x,int l,int r,int al,int ar){
	if(l>ar||r<al)return emp;//出界直接返回空 
	if(l>=al&&r<=ar)return tree[x];
	if(tree[x].tag)pushdown(x);
	int mid=l+r>>1;
	node lt=ask(x<<1,l,mid,al,ar),//左儿子 
	rt=ask(x<<1|1,mid+1,r,al,ar);//右儿子 
	node ans=emp;//赋个初值，没啥用 
	//pushup散装 
	ans.sum=lt.sum+rt.sum;
	ans.len=lt.len+rt.len;
	ans.lmax=lt.lmax;
	if(lt.lmax==lt.len)ans.lmax+=rt.lmax;
	ans.rmax=rt.rmax;
	if(rt.rmax==rt.len)ans.rmax+=lt.rmax;
	ans.ans=max(lt.rmax+rt.lmax,max(lt.ans,rt.ans));
	return ans;//ans已成型 
}
int getnum(int x,int l,int r,int al,int ar){//获取区间内 1 的个数 
	if(l>ar||r<al)return 0;
	if(l>=al&&r<=ar)return tree[x].sum;
	int mid=l+r>>1;
	return getnum(x<<1,l,mid,al,ar)+getnum(x<<1|1,mid+1,r,al,ar);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
build(1,1,n);//简单建个树 
for(int i=1,op,l0,r0,l1,r1;i<=m;i++){
	cin>>op>>l0>>r0;
	if(op==0){
		del(1,1,n,l0,r0);//区间修改(删 1) 
	}
	if(op==1){
		cin>>l1>>r1;
		int num=getnum(1,1,n,l0,r0);//获取区间内 1 的个数  
		if(num==0)continue;//为 0 的时候二分会出问题，特判掉 
		del(1,1,n,l0,r0);//删掉区间 1 
		int l=l1,r=r1;
		while(l<=r){//二分获取 0 的个数小于等于 num 的区间最大值 
			int mid=l+r>>1;
			if(mid-l1+1-ask(1,1,n,l1,mid).sum<=num)l=mid+1;
			//sum是 1 的个数，用区间长度减去 sum 则为 0 的个数 
			else r=mid-1;
		}
		add(1,1,n,l1,r);//区间修改(加 1) 
	}
	if(op==2){//区间查询输出最长的连续的 0 的长度 
		cout<<ask(1,1,n,l0,r0).ans<<'\n';
	}
}
return 0;
}