三个操作
0：区间赋值基础操作，打标记就行。
1：查询了[l1，r1]中1个数后，[l1，r1]区间赋值基础操作，然后在[l0，r0]区间修改，因为要求“脑洞治疗仪仅会尽量填补位置比较靠前的脑洞”，所以能改左子树就改左子树，再右子树。
2：区间查询最大值，因为是求最长连续0，所以代码里有点小变化。
#include<bits/stdc++.h> #define N 200003 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int sum[N<<2];//区间1的个数 int len[N<<2];//区间长度 int maxx[N<<2],lm[N<<2],rm[N<<2],mark[N<<2]; void pushup(int k) { sum[k]=sum[k<<1]+sum[k<<1|1]; len[k]=len[k<<1]+len[k<<1|1]; lm[k]=(len[k<<1]==lm[k<<1])?(lm[k<<1]+lm[k<<1|1]):lm[k<<1]; rm[k]=(len[k<<1|1]==rm[k<<1|1])?(rm[k<<1|1]+rm[k<<1]):rm[k<<1|1]; maxx[k]=max(rm[k<<1]+lm[k<<1|1],max(maxx[k<<1],maxx[k<<1|1])); } void build(int k,int l,int r) { mark[k]=-1; if(l==r){sum[k]=len[k]=1;return;} int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pushup(k); } void pushdown(int k,int l,int r) { if(mark[k]==-1)return ; int v=mark[k];mark[k]=-1; mark[k<<1]=mark[k<<1|1]=v; sum[k<<1]=len[k<<1]*v; sum[k<<1|1]=len[k<<1|1]*v; lm[k<<1]=rm[k<<1]=maxx[k<<1]=len[k<<1]*(v^1); lm[k<<1|1]=rm[k<<1|1]=maxx[k<<1|1]=len[k<<1|1]*(v^1); } void modify_zero(int k,int L,int R,int l,int r,int v)//区间赋0 { if(L>=l&&R<=r) { mark[k]=v; sum[k]=len[k]*v; lm[k]=rm[k]=maxx[k]=len[k]*(v^1); return ; } int mid=(L+R)>>1; pushdown(k,L,R); if(l<=mid)modify_zero(k<<1,L,mid,l,r,v); if(r>mid)modify_zero(k<<1|1,mid+1,R,l,r,v); pushup(k); } int num=0; void modify_one(int k,int L,int R,int l,int r,int v)//脑洞修补 { if(R<L)return; if(sum[k]==len[k])return; if(!num)return; if(len[k]-sum[k]<=num&&L>=l&&R<=r) { num-=(len[k]-sum[k]); mark[k]=1; sum[k]=len[k]*1; maxx[k]=lm[k]=rm[k]=0; return; } int mid=(L+R)>>1; pushdown(k,L,R); if(l<=mid)modify_one(k<<1,L,mid,l,r,v); if(r>mid)modify_one(k<<1|1,mid+1,R,l,r,v); pushup(k); } int query_one(int k,int L,int R,int l,int r)//查询区间1的个数 { int ans=0; if(L>=l&&R<=r)return sum[k]; int mid=(L+R)>>1; pushdown(k,L,R); if(l<=mid)ans+=query_one(k<<1,L,mid,l,r); if(r>mid)ans+=query_one(k<<1|1,mid+1,R,l,r); return ans; } int query_max(int k,int L,int R,int l,int r)//查询区间最长连续0 { if(L>=l&&R<=r)return maxx[k]; int mid=(L+R)>>1; pushdown(k,L,R); if(r<=mid)return query_max(k<<1,L,mid,l,r); else if(l>mid)return query_max(k<<1|1,mid+1,R,l,r); else return max(min(mid-l+1,rm[k<<1])+min(r-mid,lm[k<<1|1]),max(query_max(k<<1,L,mid,l,r),query_max(k<<1|1,mid+1,R,l,r))); } int main() { int n=read(),T=read(); build(1,1,n); while(T--) { int op=read(); if(op==0) { int l=read(),r=read(); modify_zero(1,1,n,l,r,0); } else if(op==1) { int l1=read(),r1=read(),l2=read(),r2=read(); num=query_one(1,1,n,l1,r1); modify_zero(1,1,n,l1,r1,0); modify_one(1,1,n,l2,r2,1); } else { int l=read(),r=read(); printf("%d ",query_max(1,1,n,l,r)); } } }