hick过了,其它没过,求助(悬赏关注)
查看原帖
hick过了,其它没过,求助(悬赏关注)
1237546
Langke_Saonian楼主2024/7/23 12:32

无语了,hick过了其它没过,求助(悬赏关注)

#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int n,m,a[N];
int max(int a,int b){return a>b?a:b;}
struct Tree{
	int add,rev,l,r;
	int num1,amax1,lmax1,rmax1;
	int num0,amax0,lmax0,rmax0;
}e[N<<2];
// definitions and comments
	#define lid id<<1
	#define rid id<<1|1
	#define l(u) e[u].l
	#define r(u) e[u].r
	#define rev(u) e[u].rev
	#define add(u) e[u].add
	#define num1(u) e[u].num1
	#define num0(u) e[u].num0
	#define lmax1(u) e[u].lmax1
	#define lmax0(u) e[u].lmax0
	#define rmax1(u) e[u].rmax1
	#define rmax0(u) e[u].rmax0
	#define amax1(u) e[u].amax1
	#define amax0(u) e[u].amax0
	//rev 标记是否翻转 
	//num1(the number of 1)
	//num0(the number of 0)
	//amax1(all max of 1)
	//amax0(all max of 0)
	//lmax1(left max of 1)
	//lmax0(left max of 0)
	//rmax1(right max of 1)
	//rmax0(right max of 0)
	/*
	add
	-1: do nothing
	0: all of number become 0
	1: all of number become 1
	*/
inline void push_up(int id){
//cout<<"a";
	{//the change of 1
		num1(id)=num1(lid)+num1(rid);
		lmax1(id)=lmax1(lid);
		if(num1(lid)==r(lid)-l(lid)+1) lmax1(id)+=lmax1(rid);
		rmax1(id)=rmax1(rid);
		if(num1(rid)==r(rid)-l(rid)+1) rmax1(id)+=rmax1(lid);
		amax1(id)=lmax1(rid)+rmax1(lid);
		amax1(id)=max(amax1(id),amax1(lid));
		amax1(id)=max(amax1(id),amax1(rid));
	}
	{//the change of 0
		num0(id)=num0(lid)+num0(rid);
		lmax0(id)=lmax0(lid);
		if(num0(lid)==r(lid)-l(lid)+1) lmax0(id)+=lmax0(rid);
		rmax0(id)=rmax0(rid);
		if(num0(rid)==r(rid)-l(rid)+1) rmax0(id)+=rmax0(lid);
		amax0(id)=lmax0(rid)+rmax0(lid);
		amax0(id)=max(amax0(id),amax0(lid));
		amax0(id)=max(amax0(id),amax0(rid));
	}
	return;
}
inline void build(int id,int l,int r){
    l(id)=l,r(id)=r,add(id)=-1;
	if(l==r){
		num0(id)=lmax0(id)=rmax0(id)=amax0(id)=a[l]==0;
		num1(id)=lmax1(id)=rmax1(id)=amax1(id)=a[l]==1;
		return;
	}
	int mid=l+r>>1;
	build(lid,l,mid),build(rid,mid+1,r);
	push_up(id);
}
inline void push_down(int id){
//cout<<"b";
	if(add(id)!=-1){
		rev(id)=0;
		if(add(id)==0){
			{//the change of lid
				add(lid)=0,rev(lid)=0;
				num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=0;
				num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=(r(lid)-l(lid)+1);
			}
			{//the change of rid 
				add(rid)=0,rev(rid)=0;
				num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=0;
				num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=(r(rid)-l(rid)+1);
			}
			add(id)=-1;
			return;
		}
		if(add(id)==1){
			{//the change of lid
				add(lid)=1,rev(lid)=0;
				num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=0;
				num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=(r(lid)-l(lid)+1);
			}
			{//the change of rid 
				add(rid)=1,rev(rid)=0;
				num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=0;
				num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=(r(rid)-l(rid)+1);
			}
			add(id)=-1;
			return;
		}
	}
	if(rev(id)){
		swap(num1(lid),num0(lid));
		swap(num1(rid),num0(rid));
        if(add(lid)!=-1) add(lid)^=1;
		else rev(lid)^=1;
		if(add(rid)!=-1) add(rid)^=1;
		else rev(add(rid))^=1;
		swap(amax1(lid),amax0(lid));
		swap(lmax1(lid),lmax0(lid));
		swap(rmax1(lid),rmax0(lid));
		swap(amax1(rid),amax0(rid));
		swap(lmax1(rid),lmax0(rid));
		swap(rmax1(rid),rmax0(rid));
		rev(id)=0;
		return; 
	}
	return;
}
inline void modify(int id,int x,int y,int q){
	push_down(id);
	if(x==l(id)&&r(id)==y){
		if(q==0){
			add(id)=0;
			num1(id)=amax1(id)=lmax1(id)=rmax1(id)=0;
			num0(id)=amax0(id)=lmax0(id)=rmax0(id)=(r(id)-l(id)+1);
			return;
		}
		if(q==1){
			add(id)=1;
			num0(id)=amax0(id)=lmax0(id)=rmax0(id)=0;
			num1(id)=amax1(id)=lmax1(id)=rmax1(id)=(r(id)-l(id)+1);
			return;
		}
		if(q==2){
			rev(id)^=1; 
			swap(num1(id),num0(id));
			swap(amax1(id),amax0(id));
			swap(lmax1(id),lmax0(id));
			swap(rmax1(id),rmax0(id));
			return;
		}
	}
	int mid=l(id)+r(id)>>1;
	if(mid<x) modify(rid,x,y,q);
	else if(mid>=y) modify(lid,x,y,q);
	else modify(lid,x,mid,q),modify(rid,mid+1,y,q);
    push_up(id);
	return;
}
inline int query1(int id,int x,int y){
	push_down(id);
	if(x==l(id)&&r(id)==y) return num1(id);
	int mid=l(id)+r(id)>>1;
	if(mid<x) return query1(rid,x,y);
	else if(mid>=y) return query1(lid,x,y);
	return query1(lid,x,mid)+query1(rid,mid+1,y);
}
inline Tree query2(int id,int x,int y){
	push_down(id);
	if(x==l(id)&&r(id)==y) return e[id];
	int mid=l(id)+r(id)>>1;
	if(mid<x) return query2(rid,x,y);
	else if(mid>=y) return query2(lid,x,y);
	else{
		Tree ret,L=query2(lid,x,mid),R=query2(rid,mid+1,y);
		ret.num1=L.num1+R.num1;
		ret.num0=L.num0+R.num0;
		ret.lmax1=L.lmax1;
		if(L.num1==L.r-L.l+1){
			ret.lmax1+=R.lmax1;
		}
		ret.lmax0=L.lmax0;
		if(L.num0==L.r-L.l+1){
			ret.lmax0+=R.lmax0;
		}
		ret.rmax1=R.rmax1;
		if(R.num1==R.r-R.l+1){
			ret.rmax1+=L.rmax1;
		}
		ret.rmax0=R.rmax0;
		if(R.num0==R.r-R.l+1){
			ret.rmax0+=L.rmax0;
		}
		ret.amax1=R.lmax1+L.rmax1;
		ret.amax1=max(ret.amax1,L.amax1);
		ret.amax1=max(ret.amax1,R.amax1);
		ret.amax0=R.lmax0+L.rmax0;
		ret.amax0=max(ret.amax0,L.amax0);
		ret.amax0=max(ret.amax0,R.amax0);
		return ret;
	}
} 
int main(){
	scanf("%d%d",&n,&m);
//	int dep=log2(n);
//	dep=pow(2,dep+1);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	while(m--){
		int x,y,op;
		scanf("%d%d%d",&op,&x,&y);
		x++;y++;
		if(op==0||op==1||op==2){
			modify(1,x,y,op);
		}else if(op==3){
			printf("%d\n",query1(1,x,y));
		}else if(op==4){
			printf("%d\n",query2(1,x,y).amax1);
		}
	}
	return 0;
}
2024/7/23 12:32
加载中...