0pts求调
查看原帖
0pts求调
490484
include13_fAKe楼主2023/11/25 13:34

写了三个中午加一个晚上,还是0pt,哪位巨佬能帮我看一下?

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

const int N=114514;
int n,m;
int a[N];
struct segment_tree{
	int l;
	int r;
	int l0;		//左起0 
	int l1;		//左起1 
	int r0;		//右起0 
	int r1;		//右起1
	int tot0;	//总共0 
	int tot1;	//总共1
	int sum0;	//连续0
	int sum1;	//连续1
	int tag; 
}tree[4*N];
void pushup(int id){
	tree[id].l0=tree[id*2].l0;
	if(tree[id*2].tot1==0){
		tree[id].l0=tree[id*2].tot0+tree[id*2+1].l0;
	}
	tree[id].r0=tree[id*2+1].r0;
	if(tree[id*2+1].tot1==0){
		tree[id].r0=tree[id*2+1].tot0+tree[id*2].r0;
	}
	tree[id].l1=tree[id*2].l1;
	if(tree[id*2].tot0==0){
		tree[id].l1=tree[id*2].tot1+tree[id*2+1].l1;
	}
	tree[id].r1=tree[id*2+1].r1;
	if(tree[id*2+1].tot0==0){
		tree[id].r1=tree[id*2+1].tot1+tree[id*2].r1;
	}
	tree[id].tot0=tree[id*2].tot0+tree[id*2+1].tot0;
	tree[id].tot1=tree[id*2].tot1+tree[id*2+1].tot1;
	tree[id].sum0=max(tree[id*2].r0+tree[id*2+1].l0,max(tree[id*2].sum0,tree[id*2+1].sum0));
	tree[id].sum1=max(tree[id*2].r1+tree[id*2+1].l1,max(tree[id*2].sum1,tree[id*2+1].sum1));
}
void pushdown(int id){
	if(tree[id].tag==-1)	return;
	if(tree[id].tag==0){
		tree[id*2].tag=0;
		tree[id*2].tot0+=tree[id*2].tot1;
		tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1=0;
		tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0;
		tree[id*2+1].tag=0;
		tree[id*2+1].tot0+=tree[id*2+1].tot1;
		tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1=0;
		tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0;
		tree[id].tag=-1;
		return;
	}
	if(tree[id].tag==1){
		tree[id*2].tag=1;
		tree[id*2].tot1+=tree[id*2].tot0;
		tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0=0;
		tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1;
		tree[id*2+1].tag=1;
		tree[id*2+1].tot1+=tree[id*2+1].tot0;
		tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0=0;
		tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1;
		tree[id].tag=-1;
		return;
	}
	if(tree[id*2].tag==2){
		tree[id*2].tag=-1;
	} 
	else if(tree[id*2].tag==1){
		tree[id*2].tag=0;
		tree[id*2].tot0+=tree[id*2].tot1;
		tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1=0;
		tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0;
	}
	else if(tree[id*2].tag==0){
		tree[id*2].tag=1;
		tree[id*2].tot1+=tree[id*2].tot0;
		tree[id*2].l0=tree[id*2].r0=tree[id*2].sum0=tree[id*2].tot0=0;
		tree[id*2].l1=tree[id*2].r1=tree[id*2].sum1=tree[id*2].tot1;
	}
	else{
		tree[id*2].tag=2;
		swap(tree[id*2].l0,tree[id*2].l1);
		swap(tree[id*2].r0,tree[id*2].r1);
		swap(tree[id*2].tot0,tree[id*2].tot1);
		swap(tree[id*2].sum0,tree[id*2].sum1);
	}
	if(tree[id*2+1].tag==2){
		tree[id*2+1].tag=-1;
	} 
	else if(tree[id*2+1].tag==1){
		tree[id*2+1].tag=0;
		tree[id*2+1].tot0+=tree[id*2+1].tot1;
		tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1=0;
		tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0;
	}
	else if(tree[id*2+1].tag==0){
		tree[id*2+1].tag=1;
		tree[id*2+1].tot1+=tree[id*2+1].tot0;
		tree[id*2+1].l0=tree[id*2+1].r0=tree[id*2+1].sum0=tree[id*2+1].tot0=0;
		tree[id*2+1].l1=tree[id*2+1].r1=tree[id*2+1].sum1=tree[id*2+1].tot1;
	}
	else{
		tree[id*2+1].tag=2;
		swap(tree[id*2+1].l0,tree[id*2+1].l1);
		swap(tree[id*2+1].r0,tree[id*2+1].r1);
		swap(tree[id*2+1].tot0,tree[id*2+1].tot1);
		swap(tree[id*2+1].sum0,tree[id*2+1].sum1);
	}
	tree[id].tag=-1;
	return;
}
void build(int id,int l,int r){
	tree[id].l=l;
	tree[id].r=r;
	tree[id].tag=-1;
	if(l==r){
		if(a[l]==0){
			tree[id].l0=1;
			tree[id].r0=1;
			tree[id].sum0=1;
			tree[id].tot0=1;
		}
		else{
			tree[id].l1=1;
			tree[id].r1=1;
			tree[id].sum1=1;
			tree[id].tot1=1;
		}
		return;
	}
	int mid=l+r>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id);
}
void query0(int id,int l,int r){
	int l2=tree[id].l;
	int r2=tree[id].r;
	if(l2>=l&&r2<=r){
		tree[id].tag=0;
		tree[id].tot0+=tree[id].tot1;
		tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1=0;
		tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0;
		return;
	}
	pushdown(id);
	int mid=l2+r2>>1;
	if(l<=mid)	query0(id*2,l,r);
	if(r>mid)	query0(id*2+1,l,r);
	pushup(id);
}
void query1(int id,int l,int r){
	int l2=tree[id].l;
	int r2=tree[id].r;
	if(l2>=l&&r2<=r){
		tree[id].tag=1;
		tree[id].tot1+=tree[id].tot0;
		tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0=0;
		tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1;
		return;
	}
	pushdown(id);
	int mid=l2+r2>>1;
	if(l<=mid)	query1(id*2,l,r);
	if(r>mid)	query1(id*2+1,l,r);
	pushup(id);
}
void query2(int id,int l,int r){
	int l2=tree[id].l;
	int r2=tree[id].r;
	if(l2>=l&&r2<=r){
//		cout<<l2<<' '<<r2<<endl; 
		if(tree[id].tag==2)	tree[id].tag=-1;
		else if(tree[id].tag==1){
			tree[id].tag=0;
			tree[id].tot0+=tree[id].tot1;
			tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1=0;
			tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0;
		}
		else if(tree[id].tag==0){
			tree[id].tag=1;
			tree[id].tot1+=tree[id].tot0;
			tree[id].l0=tree[id].r0=tree[id].sum0=tree[id].tot0=0;
			tree[id].l1=tree[id].r1=tree[id].sum1=tree[id].tot1;	
		}
		else{
			tree[id].tag=2;
			swap(tree[id].l0,tree[id].l1);
			swap(tree[id].r0,tree[id].r1);
			swap(tree[id].tot0,tree[id].tot1);
			swap(tree[id].sum0,tree[id].sum1);
		}
		return;
	}
	pushdown(id);
	int mid=l2+r2>>1;
	if(l<=mid)	query2(id*2,l,r);
	if(r>mid)	query2(id*2+1,l,r);
	pushup(id);
} 
int query3(int id,int l,int r){
	int l2=tree[id].l;
	int r2=tree[id].r;
	if(l2>=l&&r2<=r){
		return tree[id].tot1;
	}
	pushdown(id);
	int mid=l2+r2>>1;
	int ans=0;
	if(l<=mid)	ans+=query3(id*2,l,r);
	if(r>mid)	ans+=query3(id*2+1,l,r);
	pushup(id);
	return ans;
}
segment_tree query4(int id,int l,int r){
	int l2=tree[id].l;
	int r2=tree[id].r;
	if(l2>=l&&r2<=r){
		return tree[id];
	}
	pushdown(id);
	int mid=l2+r2>>1;
	segment_tree ret,ret1,ret2;
	if(r<=mid)	return query4(id*2,l,r);
	if(l>mid)	return query4(id*2+1,l,r);
	ret1=query4(id*2,l,r);
	ret2=query4(id*2+1,l,r);
	ret.l0=ret1.l0;
	if(ret1.tot1==0){
		ret.l0=ret1.tot0+ret2.l0;
	}
	ret.r0=ret2.r0;
	if(ret2.tot1==0){
		ret.r0=ret2.tot0+ret1.r0;
	}
	ret.l1=ret1.l1;
	if(ret1.tot0==0){
		ret.l1=ret1.tot1+ret2.l1;
	}
	ret.r1=ret2.r1;
	if(ret2.tot0==0){
		ret.r1=ret2.tot1+ret1.r1;
	}
	ret.tot0=ret1.tot0+ret2.tot0;
	ret.tot1=ret1.tot1+ret2.tot1;
	ret.sum0=max(ret1.r0+ret2.l0,max(ret1.sum0,ret2.sum0));
	ret.sum1=max(ret1.r1+ret2.l1,max(ret1.sum1,ret2.sum1));
	return ret;
}
int main(){ 
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	build(1,0,n-1);
	while(m--){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		switch(op){
			case 0:query0(1,l,r);break;
			case 1:query1(1,l,r);break;
			case 2:query2(1,l,r);break;
			case 3:printf("%d\n",query3(1,l,r));break;
			case 4:printf("%d\n",query4(1,l,r).sum1);break;
		}
	}
	return 0;
}

多谢了。

2023/11/25 13:34
加载中...