Hack数据过,讨论区的hack也都过了,但是还是0分,急,玄关
查看原帖
Hack数据过,讨论区的hack也都过了,但是还是0分,急,玄关
923248
Lian_zy楼主2024/12/14 21:39

rt,找了好久错了,还是不知道错在哪

Subtask#1的一个点AC了

#include<bits/stdc++.h>
#define N 100005
using namespace std;

//区间变0/1 ->tag
//区间取反 ->puttag
//区间和 ->sum0/sum1
//区间最长连续1 ->ans0,ans1,rmx0,rmx1,lmx0,lmx1
struct node{
	int l,r;
	int sum0,sum1;
	int ans0,ans1,rmx0,rmx1,lmx0,lmx1;
	int tag,puttag;
}none,t[N<<2];
int n,m,x,y,z,a[N];
node push_up(node ans,node ls,node rs){
	ans.sum0=ls.sum0+rs.sum0;
	ans.sum1=ls.sum1+rs.sum1;
	//从左/右起最长的连续0/1 
	//left
	ans.lmx0=ls.lmx0+(ls.lmx0==ls.r-ls.l+1)*rs.lmx0;
	ans.lmx1=ls.lmx1+(ls.lmx1==ls.r-ls.l+1)*rs.lmx1;
	//right
	ans.rmx0=rs.rmx0+(rs.rmx0==rs.r-rs.l+1)*ls.rmx0;
	ans.rmx1=rs.rmx1+(rs.rmx1==rs.r-rs.l+1)*ls.rmx1;
	//获取ans 
	ans.ans0=max(max(ls.ans0,rs.ans0),ls.rmx0+rs.lmx0); 
	ans.ans1=max(max(ls.ans1,rs.ans1),ls.rmx1+rs.lmx1);
	return ans; 
}
void push_down(int x){
	//先赋值再取反
	if(~t[x].puttag){//处理区间赋值标记 
		if(t[x].puttag){//标记:区间赋1 
			t[x<<1].ans0=0;
			t[x<<1].lmx0=0;
			t[x<<1].rmx0=0;
			t[x<<1].sum0=0;
			t[x<<1].ans1=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].lmx1=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].rmx1=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].sum1=t[x<<1].r-t[x<<1].l+1;
			t[x<<1|1].ans0=0;
			t[x<<1|1].lmx0=0;
			t[x<<1|1].rmx0=0;
			t[x<<1|1].sum0=0;
			t[x<<1|1].ans1=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].lmx1=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].rmx1=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].sum1=t[x<<1|1].r-t[x<<1|1].l+1;
		}else{//区间赋0 
			t[x<<1].ans1=0;
			t[x<<1].lmx1=0;
			t[x<<1].rmx1=0;
			t[x<<1].sum1=0;
			t[x<<1].ans0=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].lmx0=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].rmx0=t[x<<1].r-t[x<<1].l+1;
			t[x<<1].sum0=t[x<<1].r-t[x<<1].l+1;
			t[x<<1|1].ans1=0;
			t[x<<1|1].lmx1=0;
			t[x<<1|1].rmx1=0;
			t[x<<1|1].sum1=0;
			t[x<<1|1].ans0=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].lmx0=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].rmx0=t[x<<1|1].r-t[x<<1|1].l+1;
			t[x<<1|1].sum0=t[x<<1|1].r-t[x<<1|1].l+1;
		}
		//下传
		//覆盖掉取反标记 
		t[x<<1].tag=0;
		t[x<<1|1].tag=0;
		//下传
		t[x<<1].puttag=t[x].puttag;
		t[x<<1|1].puttag=t[x].puttag;
		//标记清空
		t[x].puttag=-1; 
	}
	if(t[x].tag){//处理区间取反 
		//取反
		if(t[x].tag^t[x<<1].tag){
			swap(t[x<<1].ans0,t[x<<1].ans1);
			swap(t[x<<1].lmx0,t[x<<1].lmx1);
			swap(t[x<<1].rmx0,t[x<<1].rmx1);
			swap(t[x<<1].sum0,t[x<<1].sum1);
		}
		if(t[x].tag^t[x<<1|1].tag){
			swap(t[x<<1|1].ans0,t[x<<1|1].ans1);
			swap(t[x<<1|1].lmx0,t[x<<1|1].lmx1);
			swap(t[x<<1|1].rmx0,t[x<<1|1].rmx1);
			swap(t[x<<1|1].sum0,t[x<<1|1].sum1);
		}
		//下传
		t[x<<1].tag^=t[x].tag;
		t[x<<1|1].tag^=t[x].tag;
		//标记清空
		t[x].tag=0; 
	}
	return;
}
void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	t[x].puttag=-1;
	if(l==r){
		if(a[l]){
			t[x].ans1=1;
			t[x].sum1=1;
			t[x].rmx1=1;
			t[x].lmx1=1;
		}else{
			t[x].ans0=1;
			t[x].sum0=1;
			t[x].rmx0=1;
			t[x].lmx0=1;
		}
		return;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
	return;
}
void change(int x,int l,int r,int d){
	int L=t[x].l;
	int R=t[x].r;
	if(l<=L&&R<=r){
		t[x].puttag=d;
		t[x].tag=0;
		if(d){
			t[x].ans0=0;
			t[x].lmx0=0;
			t[x].rmx0=0;
			t[x].sum0=0;
			t[x].ans1=t[x].r-t[x].l+1;
			t[x].lmx1=t[x].r-t[x].l+1;
			t[x].rmx1=t[x].r-t[x].l+1;
			t[x].sum1=t[x].r-t[x].l+1;
		}else{
			t[x].ans1=0;
			t[x].lmx1=0;
			t[x].rmx1=0;
			t[x].sum1=0;
			t[x].ans0=t[x].r-t[x].l+1;
			t[x].lmx0=t[x].r-t[x].l+1;
			t[x].rmx0=t[x].r-t[x].l+1;
			t[x].sum0=t[x].r-t[x].l+1;
		}
		return;
	}
	push_down(x);
	int mid=L+R>>1;
	if(l<=mid)change(x<<1,l,r,d);
	if(r>mid)change(x<<1|1,l,r,d);
	t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
	return;
}
void update(int x,int l,int r){
	int L=t[x].l;
	int R=t[x].r;
	if(l<=L&&R<=r){
		t[x].tag^=1;
		swap(t[x].ans0,t[x].ans1);
		swap(t[x].lmx0,t[x].lmx1);
		swap(t[x].rmx0,t[x].rmx1);
		swap(t[x].sum0,t[x].sum1);
		return;
	}
	push_down(x);
	int mid=L+R>>1;
	if(l<=mid)update(x<<1,l,r);
	if(r>mid) update(x<<1|1,l,r);
	t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
	return;
}
node query(int x,int l,int r){
	int L=t[x].l;
	int R=t[x].r;
	if(l<=L&&R<=r)return t[x];
	push_down(x);
	node left=none;
	node right=none;
	bool lf=0,rt=0;
	int mid=L+R>>1;
	if(l<=mid)left=query(x<<1,l,r),lf=1;
	if(r>mid) right=query(x<<1|1,l,r),rt=1;
	if(lf&&rt)return push_up(none,left,right);
	if(lf)return left;
	return right;
}
void print_tree(int x){
	int L=t[x].l;
	int R=t[x].r;
	cout<<x<<' '<<L<<' '<<R<<endl;
	cout<<"ans "<<t[x].ans0<<' '<<t[x].ans1<<endl;
	cout<<"sum "<<t[x].sum0<<' '<<t[x].sum1<<endl;
	cout<<"lmx "<<t[x].lmx0<<' '<<t[x].lmx1<<endl;
	cout<<"rmx "<<t[x].rmx0<<' '<<t[x].rmx1<<endl;
	if(L==R)return;
	cout<<"ls "<<x*2<<' '<<"rs"<<x*2+1<<endl;
	print_tree(x<<1);
	print_tree(x<<1|1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	build(1,1,n);
	//print_tree(1);
	while(m--){
		scanf("%d%d%d",&x,&y,&z);
		y++;
		z++;
		if(x==0)change(1,y,z,0);
		if(x==1)change(1,y,z,1);
		if(x==2)update(1,y,z);
		if(x==3)printf("%d\n",query(1,y,z).sum1);
		if(x==4)printf("%d\n",query(1,y,z).ans1);
		//puts("NOWTREE");
		//print_tree(1);
	}
	return 0;
} 
2024/12/14 21:39
加载中...