社区讨论

萌新求助

mmuyang_233
P2572[SCOI2010] 序列操作参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo7ujuoc
此快照首次捕获于
2023/10/27 08:00
2 年前
此快照最后确认于
2023/10/27 08:00
2 年前
查看原帖
RT\text{RT}，实在看不出来哪里错了/kk
20pts20\text{pts} AC 1 2 11\color{green}\text{AC 1 2 11}
CPP
#include <cstring>
using namespace std;
struct TREE{
	int sum0,sum1;
	int lsum0,lsum1;
	int rsum0,rsum1;
	int maxsum0,maxsum1;
	int cov,rev;
}Tree[400005];
int n,m;
TREE uni;
int a[100005];
inline void input(int &x){
	x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
}
void write(int x){
	if (x<10){
		putchar((char)(x+'0'));return;
	}
	write(x/10);
	putchar((char)(x%10+'0'));
}
inline void output(int x,char c){
	write(x);putchar(c);
}
inline int max(int a,int b){
	return a>b?a:b;
}
inline void swap(int &x,int &y){
	int t=x;x=y;y=t;
}
inline void init(){
	uni.sum0=uni.sum1=uni.lsum0=uni.lsum1=uni.rsum0=uni.rsum1=uni.maxsum0=uni.maxsum1=0;
	uni.cov=uni.rev=-1;
}
inline void pushup(int l,int r,int id){
	int mid=(l+r)>>1;
	Tree[id].sum0=Tree[id<<1].sum0+Tree[id<<1|1].sum0;
	Tree[id].sum1=Tree[id<<1].sum1+Tree[id<<1|1].sum1;
	if (Tree[id<<1].lsum0){
		Tree[id].lsum1=0;
		Tree[id].lsum0=Tree[id<<1].lsum0;
		if (Tree[id<<1].sum0==mid-l+1) Tree[id].lsum0+=Tree[id<<1|1].lsum0;
	}
	else{
		Tree[id].lsum0=0;
		Tree[id].lsum1=Tree[id<<1].lsum1;
		if (Tree[id<<1].sum1==mid-l+1) Tree[id].lsum1+=Tree[id<<1|1].lsum1;
	}
	if (Tree[id<<1|1].rsum0){
		Tree[id].rsum1=0;
		Tree[id].rsum0=Tree[id<<1|1].rsum0;
		if (Tree[id<<1|1].sum0==r-mid) Tree[id].rsum0+=Tree[id<<1].rsum0;
	}
	else{
		Tree[id].rsum0=0;
		Tree[id].rsum1=Tree[id<<1|1].rsum1;
		if (Tree[id<<1|1].sum1==r-mid) Tree[id].rsum1+=Tree[id<<1].rsum1;
	}
	Tree[id].maxsum0=max(max(Tree[id<<1].maxsum0,Tree[id<<1|1].maxsum0),Tree[id<<1].rsum0+Tree[id<<1|1].lsum0);
	Tree[id].maxsum1=max(max(Tree[id<<1].maxsum1,Tree[id<<1|1].maxsum1),Tree[id<<1].rsum1+Tree[id<<1|1].lsum1);
}
inline void pushdown(int l,int r,int id){
	int mid=(l+r)>>1;
	if (Tree[id].cov!=-1){
		Tree[id<<1].cov=Tree[id<<1|1].cov=Tree[id].cov;
		Tree[id<<1].rev=Tree[id<<1|1].rev=-1;
		if (!Tree[id].cov){
			Tree[id<<1].sum0=Tree[id<<1].lsum0=Tree[id<<1].rsum0=Tree[id<<1].maxsum0=mid-l+1;
			Tree[id<<1].sum1=Tree[id<<1].lsum1=Tree[id<<1].rsum1=Tree[id<<1].maxsum1=0;
			Tree[id<<1|1].sum0=Tree[id<<1|1].lsum0=Tree[id<<1|1].rsum0=Tree[id<<1|1].maxsum0=r-mid;
			Tree[id<<1|1].sum1=Tree[id<<1|1].lsum1=Tree[id<<1|1].rsum1=Tree[id<<1|1].maxsum1=0;
		}
		else{
			Tree[id<<1].sum0=Tree[id<<1].lsum0=Tree[id<<1].rsum0=Tree[id<<1].maxsum0=0;
			Tree[id<<1].sum1=Tree[id<<1].lsum1=Tree[id<<1].rsum1=Tree[id<<1].maxsum1=mid-l+1;
			Tree[id<<1|1].sum0=Tree[id<<1|1].lsum0=Tree[id<<1|1].rsum0=Tree[id<<1|1].maxsum0=0;
			Tree[id<<1|1].sum1=Tree[id<<1|1].lsum1=Tree[id<<1|1].rsum1=Tree[id<<1|1].maxsum1=r-mid;
		}
		Tree[id].cov=Tree[id].rev=-1;
	}
	if (Tree[id].rev!=-1){
		Tree[id<<1].rev*=-1;
		Tree[id<<1|1].rev*=-1;
		if (Tree[id<<1].cov!=-1) Tree[id<<1].cov^=1;
		if (Tree[id<<1|1].cov!=-1) Tree[id<<1|1].cov^=1;
		swap(Tree[id<<1].sum0,Tree[id<<1].sum1);
		swap(Tree[id<<1|1].sum0,Tree[id<<1|1].sum1);
		swap(Tree[id<<1].lsum0,Tree[id<<1].lsum1);
		swap(Tree[id<<1|1].lsum0,Tree[id<<1|1].lsum1);
		swap(Tree[id<<1].rsum0,Tree[id<<1].rsum1);
		swap(Tree[id<<1|1].rsum0,Tree[id<<1|1].rsum1);
		swap(Tree[id<<1].maxsum0,Tree[id<<1].maxsum1);
		swap(Tree[id<<1|1].maxsum0,Tree[id<<1|1].maxsum1);
		Tree[id].rev=-1;
	}
}
void build(int l,int r,int id){
	Tree[id]=uni;
	if (l==r){
		if (!a[l]){
			Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=1;
		}
		else{
			Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=1;
		}
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
	pushup(l,r,id);
} 
void update1(int x,int y,int k,int l,int r,int id){
	if (x<=l&&r<=y){
		Tree[id].cov=k;Tree[id].rev=-1;
		if (!k) {
			Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=r-l+1;
			Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=0;
		}
		else{
			Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=0;
			Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=r-l+1;
		}
		return;
	}
	pushdown(l,r,id);
	int mid=(l+r)>>1;
	if (x<=mid) update1(x,y,k,l,mid,id<<1);
	if (y>mid) update1(x,y,k,mid+1,r,id<<1|1);
	pushup(l,r,id);
}
void update2(int x,int y,int l,int r,int id){
	if (x<=l&&r<=y){
		Tree[id].rev*=-1;
		swap(Tree[id].sum0,Tree[id].sum1);
		swap(Tree[id].lsum0,Tree[id].lsum1);
		swap(Tree[id].rsum0,Tree[id].rsum1);
		swap(Tree[id].maxsum0,Tree[id].maxsum1);
		return;
	}
	pushdown(l,r,id);
	int mid=(l+r)>>1;
	if (x<=mid) update2(x,y,l,mid,id<<1);
	if (y>mid) update2(x,y,mid+1,r,id<<1|1);
	pushup(l,r,id);
}
int query1(int x,int y,int l,int r,int id){
	if (x<=l&&r<=y){
		return Tree[id].sum1;
	}
	pushdown(l,r,id);
	int mid=(l+r)>>1,res=0;
	if (x<=mid) res+=query1(x,y,l,mid,id<<1);
	if (y>mid) res+=query1(x,y,mid+1,r,id<<1|1);
	return res;
}
TREE query2(int x,int y,int l,int r,int id){
	if (x<=l&&r<=y){
		return Tree[id];
	}
	pushdown(l,r,id);
	int mid=(l+r)>>1;
	TREE res=uni,res1=uni,res2=uni;
	if (x<=mid) res1=query2(x,y,l,mid,id<<1);
	if (y>mid) res2=query2(x,y,mid+1,r,id<<1|1);
	res.sum1=res1.sum1+res2.sum1;
	res.lsum1=res1.lsum1;
	if (res1.sum1==mid-l+1) res.lsum1+=res2.lsum1;
	res.rsum1=res2.rsum1;
	if (res2.sum1==r-mid) res.rsum1+=res1.rsum1;
	res.maxsum1=max(max(res1.maxsum1,res2.maxsum1),res1.rsum1+res2.lsum1);
	return res;
}
int main(){
	init();
	input(n);input(m);
	for (int i=1;i<=n;i++){
		input(a[i]);
	}
	build(1,n,1);
	while(m--){
		int opt,l,r;
		input(opt);input(l);input(r);
		++l;++r;
		switch(opt){
			case 0:
				update1(l,r,0,1,n,1);break;
			case 1:
				update1(l,r,1,1,n,1);break;
			case 2:
				update2(l,r,1,n,1);break;
			case 3:
				output(query1(l,r,1,n,1),'\n');break;
			case 4:
				output(query2(l,r,1,n,1).maxsum1,'\n');break;
		}
	}
	return 0;
}

回复

共 5 条回复，欢迎继续交流。

正在加载回复...