T2

# include<iostream>
using namespace std;

const int N=3e5+2;
int n,a[N],t[N],id[N];

struct note{
	int val,id;
	note(int x,int y){
		val=x,id=y;
	}
};

void build(int i,int l,int r){
	if(l==r) t[i]=a[l],id[N]=l;
	int mid=(l+r)/2;
	build(2*i,l,mid);
	build(2*i+1,mid+1,r);
}

note find(int i,int l,int r,int x,int y){
	if(x<=l&&r<=y) return note(t[i],id[i]);
	int mid=(l+r)/2,ans,idd;
	note tmp;
	if(x<=mid){
		tmp=find(2*i,l,mid,x,y);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	return 0;
}

T3 P2572

洛谷题面

洛谷题解

# include<iostream>
using namespace std;

const int N=1e5+5;

struct d{
	int n0,n1; //总共的0/1个数
	int l0,l1; //左起连续的0/1个数
	int r0,r1; //右起连续的0/1个数
	int s0,s1; //区间总共的0/1个数 
	d(int n0=0,int n1=0,int l0=0,int l1=0,
	int r0=0,int r1=0,int s0=0,int s1=0):
	n0(n0),n1(n1),l0(l0),l1(l1),
	r0(r0),r1(r1),s0(s0),s1(s1){} 
}t[4*N]; //区间信息存储 

int n,m,op,x,y,a[N],len[4*N];
int tgval[4*N],tgswp[4*N]; //赋值和取反tag 

d merge(d t1,d t2){
	return d(t1.n0+t2.n0,t1.n1+t2.n1,
	(t1.n1?t1.l0:t1.l0+t2.l0),(t1.n0?t1.l1:t1.l1+t2.l1),
	(t2.n1?t2.r0:t1.r0+t2.r0),(t2.n0?t2.r1:t1.r1+t2.r1),
	max(max(t1.s0,t2.s0),t1.r0+t2.l0),
	max(max(t1.s1,t2.s1),t1.r1+t2.l1));
} //区间合并 

void change(int i,int op){
	int len=t[i].n0+t[i].n1;
	if(op==0){
		tgval[i]=tgswp[i]=0;
		t[i]=d(len,0,len,0,len,0,len,0);
	}
	else if(op==1){
		tgval[i]=1,tgswp[i]=0;
		t[i]=d(0,len,0,len,0,len,0,len);
	}
	else if(op==2){
		tgswp[i]^=1;
		t[i]=d(t[i].n1,t[i].n0,t[i].l1,t[i].l0,
		t[i].r1,t[i].r0,t[i].s1,t[i].s0);
	}
} //区间修改+打标记 

void pushdown(int i){
	if(tgval[i]!=-1)
		change(2*i,tgval[i]),change(2*i+1,tgval[i]);
	if(tgswp[i])
		change(2*i,2),change(2*i+1,2);
	tgval[i]=-1,tgswp[i]=0;
} //标记下传 

void build(int l,int r,int i){
	tgval[i]=-1; //tag初始化
	if(l==r){
		if(a[l]) t[i]=d(0,1,0,1,0,1,0,1);
		else t[i]=d(1,0,1,0,1,0,1,0);
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	t[i]=merge(t[2*i],t[2*i+1]);
} 

void update(int l,int r,int i,int x,int y,int op){
	if(y<l||r<x) return;
	if(x<=l&&r<=y){
		change(i,op);
		return;
	}
	int mid=(l+r)/2;
	pushdown(i);
	update(l,mid,2*i,x,y,op);
	update(mid+1,r,2*i+1,x,y,op);
	t[i]=merge(t[2*i],t[2*i+1]);
}

d query(int l,int r,int i,int x,int y){
	if(y<l||r<x) return d();
	if(x<=l&&r<=y) return t[i];
	int mid=(l+r)/2;
	pushdown(i);
	return merge(query(l,mid,2*i,x,y),
	query(mid+1,r,2*i+1,x,y));
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,1);
	while(m--){
		cin>>op>>x>>y;
		++x,++y; //下标从0开始 
		if(op<3) update(1,n,1,x,y,op);
		else{
			d tmp=query(1,n,1,x,y);
			if(op==3) cout<<tmp.n1<<endl;
			else cout<<tmp.s1<<endl;
		}
	}
	return 0;
}