社区讨论

超级无敌史山代码求条，仅过了hack

yyangqy1919
P2572[SCOI2010] 序列操作参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mk8lbxdi
此快照首次捕获于
2026/01/11 01:40
上个月
此快照最后确认于
2026/01/14 16:40
上个月
查看原帖
rt，调了我足足一个晚上直到现在我还是不知道怎么改，代码可能很难看懂，希望大佬们能尽量帮我找出错误球球了，一个明显的错误是query_2我根本不会考虑合并区间产生新串的该怎么写，其他错误我也找不到了，尽力了。。。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool a[100010];
struct node{
	int l,r,ls,rs,sum,pre0,pre1,rea1,rea0,ans0,ans1;
	int tag0,tag1,tag2;//tag0表示修改0的懒标记，tag1表示修改1的懒标记，tag2表示对这个区间进行取反的懒标记 
}tree[400010];
void pushup(int l,int r,int p){ 
	int mid=(l+r)>>1;
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
	if(tree[p*2].rs==tree[p*2+1].ls){
		if(tree[p*2].rs==1){//这些都是区间合并 考虑到了可能的区间合并导致的出现更大的连续串的情况，并且可以不止运用于建树操作 
			if(tree[p*2].pre1==mid-l+1) tree[p].pre1=max(tree[p*2].pre1,tree[p*2].pre1+tree[p*2+1].pre1);
			if(tree[p*2+1].rea1==r-mid) tree[p].rea1=max(tree[p*2].rea1,tree[p*2].rea1+tree[p*2+1].rea1);
			tree[p].ans1=max(tree[p*2].ans1,tree[p*2].rea1+tree[p*2+1].pre1);
			tree[p].pre0=max(max(tree[p].pre0,tree[p*2].pre0),tree[p*2+1].pre0);
			tree[p].pre1=max(max(tree[p].pre1,tree[p*2].pre1),tree[p*2+1].pre1);
			tree[p].rea0=max(max(tree[p].rea0,tree[p*2].rea0),tree[p*2+1].rea0);
			tree[p].rea1=max(max(tree[p].rea1,tree[p*2].rea1),tree[p*2+1].rea1);
		}else{
			if(tree[p*2].pre0==mid-l+1) tree[p].pre0=max(tree[p*2].pre0,tree[p*2].pre0+tree[p*2+1].pre0);
			if(tree[p*2+1].rea0==r-mid) tree[p].rea0=max(tree[p*2].rea0,tree[p*2].rea0+tree[p*2+1].rea0);
			tree[p].ans0=max(tree[p*2].ans0,tree[p*2].rea0+tree[p*2+1].pre0);
			tree[p].pre0=max(max(tree[p].pre0,tree[p*2].pre0),tree[p*2+1].pre0);
			tree[p].pre1=max(max(tree[p].pre1,tree[p*2].pre1),tree[p*2+1].pre1);
			tree[p].rea0=max(max(tree[p].rea0,tree[p*2].rea0),tree[p*2+1].rea0);
			tree[p].rea1=max(max(tree[p].rea1,tree[p*2].rea1),tree[p*2+1].rea1);
		}
	}else{
		tree[p].ans0=max(tree[p*2].ans0,tree[p*2+1].ans0);
		tree[p].ans1=max(tree[p*2].ans1,tree[p*2+1].ans1);
		tree[p].pre0=max(max(tree[p].pre0,tree[p*2].pre0),tree[p*2+1].pre0);//神奇选最大值操作 
		tree[p].pre1=max(max(tree[p].pre1,tree[p*2].pre1),tree[p*2+1].pre1);
		tree[p].rea0=max(max(tree[p].rea0,tree[p*2].rea0),tree[p*2+1].rea0);
		tree[p].rea1=max(max(tree[p].rea1,tree[p*2].rea1),tree[p*2+1].rea1);
	}
}
//0 0 0 1 1
//         [1,5]        [1,2][3,4] {<---2][3--->}-->[1,4]
//    [1,3]    [4,5]
// [1,2][3,3][4,4][5,5]
//[1][2] //[1,2] [1]+[2]'s pre==r-mid+1
//0 0    //l=1,r=2,mid=1,r-mid+1=2
//       //l=1,r=10,mid=5,r-mid+1=6
//1 1 1 1 0
//[1,4]
//[1,3] [4,4]
//tree[8].pre0=tree[8].rea0=1
//tree[9].pre0=tree[9].rea0=1
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	tree[p].ls=a[l],tree[p].rs=a[r];
	if(l==r){
		tree[p].sum=a[l];
		if(a[l]) tree[p].pre1=tree[p].rea1=tree[p].ans1=1;
		else tree[p].pre0=tree[p].rea0=tree[p].ans0=1;
		return;
	}
	int mid=(l+r)>>1;
	//cout<<l<<" "<<r<<" "<<mid<<endl;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(l,r,p);
}
void pushdown(int l,int r,int p){
	int mid=(l+r)>>1;
	if(tree[p].tag1){
		//cout<<tree[p].l<<":"<<tree[p].r<<endl;
		tree[p*2].rea1=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].pre1=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].ans1=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].sum=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].pre0=0;
		tree[p*2].rea0=0;
		tree[p*2].ans0=0;
		tree[p*2].tag0=0;
		tree[p*2].tag1=1;
		tree[p*2].tag2=0;//将标签和相关属性转移到左侧的线段树子树中 
		tree[p*2].ls=1;
		tree[p*2].rs=1;
		tree[p*2+1].rea1=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].pre1=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].ans1=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].sum=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].pre0=0;
		tree[p*2+1].rea0=0;
		tree[p*2+1].ans0=0;
		tree[p*2+1].tag0=0;
		tree[p*2+1].tag1=1;
		tree[p*2+1].tag2=0;//将标签和相关属性转移到右侧的线段树子树中 
		tree[p*2+1].ls=1;
		tree[p*2+1].rs=1;
		tree[p].tag0=0;
		tree[p].tag1=0;
		tree[p].tag2=0;
	}
	if(tree[p].tag0){
		tree[p*2].rea0=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].pre0=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].ans0=tree[p*2].r-tree[p*2].l+1;
		tree[p*2].pre1=0;
		tree[p*2].rea1=0;
		tree[p*2].ans1=0;
		tree[p*2].tag0=1;
		tree[p*2].tag1=0;
		tree[p*2].tag2=0;//将标签和相关属性转移到左侧的线段树子树中 
		tree[p*2].ls=0;
		tree[p*2].rs=0;
		tree[p*2+1].rea0=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].pre0=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].ans0=tree[p*2+1].r-tree[p*2+1].l+1;
		tree[p*2+1].pre1=0;
		tree[p*2+1].rea1=0;
		tree[p*2+1].ans1=0;
		tree[p*2+1].tag0=1;
		tree[p*2+1].tag1=0;
		tree[p*2+1].tag2=0;//将标签和相关属性转移到右侧的线段树子树中 
		tree[p*2+1].ls=0;
		tree[p*2+1].rs=0;
		tree[p].tag0=0;
		tree[p].tag1=0;
		tree[p].tag2=0;
	}
	if(tree[p].tag2){
		//if(tree[p*2+1].tag0||tree[p*2+1].tag1) 
		//cout<<"check"<<endl;
		swap(tree[p*2].pre0,tree[p*2].pre1);
		swap(tree[p*2].rea0,tree[p*2].rea1);
		swap(tree[p*2].ans0,tree[p*2].ans1);
		tree[p*2].sum=(tree[p*2].r-tree[p*2].l+1-tree[p*2].sum);
		tree[p*2].ls!=tree[p*2].ls;
		tree[p*2].rs!=tree[p*2].rs;
		tree[p*2].tag2=1;
		if(tree[p*2].tag1) tree[p*2].tag1=0,tree[p*2].tag0=1,tree[p*2].tag2=0;
		else if(tree[p*2].tag0) tree[p*2].tag1=1,tree[p*2].tag0=0,tree[p*2].tag2=0;
		//tree[p*2].tag1=0;
		//tree[p*2].tag0=0;
		swap(tree[p*2+1].pre0,tree[p*2+1].pre1);
		swap(tree[p*2+1].rea0,tree[p*2+1].rea1);
		swap(tree[p*2+1].ans0,tree[p*2+1].ans1);
		tree[p*2+1].sum=(tree[p*2+1].r-tree[p*2+1].l+1-tree[p*2+1].sum);
		tree[p*2+1].ls!=tree[p*2+1].ls;
		tree[p*2+1].rs!=tree[p*2+1].rs;
		tree[p*2+1].tag2=1;
		if(tree[p*2+1].tag1) tree[p*2+1].tag1=0,tree[p*2+1].tag0=1,tree[p*2+1].tag2=0;
		else if(tree[p*2+1].tag0) tree[p*2+1].tag1=1,tree[p*2+1].tag0=0,tree[p*2+1].tag2=0;
	}
}
void change_0(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].tag0=1;
		tree[p].tag1=0;
		tree[p].tag2=0;
		tree[p].pre1=0;
		tree[p].rea1=0;
		tree[p].pre0=tree[p].r-tree[p].l+1;
		tree[p].rea0=tree[p].r-tree[p].l+1;
		tree[p].ans1=0;
		tree[p].ans0=tree[p].r-tree[p].l+1;
		tree[p].sum=0;
		tree[p].ls=0;
		tree[p].rs=0;
		return;
	}
	pushdown(tree[p].l,tree[p].r,p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) change_0(p*2,l,r);
	if(r>mid) change_0(p*2+1,l,r);
	pushup(tree[p].l,tree[p].r,p);
}
void change_1(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].tag1=1;
		tree[p].tag0=0;
		tree[p].tag2=0;
		tree[p].pre1=tree[p].r-tree[p].l+1;
		tree[p].rea1=tree[p].r-tree[p].l+1;
		tree[p].pre0=0;
		tree[p].rea0=0;
		tree[p].ans1=tree[p].r-tree[p].l+1;
		tree[p].ans0=0;
		tree[p].sum=tree[p].r-tree[p].l+1;//tree[p].sum的值意味着这个区间内现在有的1的个数，还是很重要的
		tree[p].ls=1;
		tree[p].rs=1; 
		return;
	}
	//cout<<tree[p].l<<" "<<tree[p].r<<endl;
	pushdown(tree[p].l,tree[p].r,p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) change_1(p*2,l,r);
	if(r>mid) change_1(p*2+1,l,r);
	pushup(tree[p].l,tree[p].r,p);
}
void change_2(int p,int l,int r){
	//cout<<l<<" "<<r<<" "<<tree[p].l<<" "<<tree[p].r<<endl;
	if(tree[p].l>=l&&tree[p].r<=r){
		//node ls=tree[p];
		tree[p].tag2=1;
		if(tree[p].tag1) tree[p].tag1=0,tree[p*2].tag0=1,tree[p].tag2=0;
		else if(tree[p].tag0) tree[p].tag1=1,tree[p].tag0=0,tree[p].tag2=0;
		//int len=tree[p].r-tree[p].l+1;
		tree[p].sum=(tree[p].r-tree[p].l+1-tree[p].sum);
		//tree[p].sum=len;
		//tree[p].sum-=ls;
		swap(tree[p].pre0,tree[p].pre1);
		swap(tree[p].rea0,tree[p].rea1);
		swap(tree[p].ans0,tree[p].ans1);
		tree[p].ls=!tree[p].ls;
		tree[p].rs=!tree[p].rs;
		//cout<<ls<<endl;
		return;
	}
	pushdown(tree[p].l,tree[p].r,p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) change_2(p*2,l,r);
	if(r>mid) change_2(p*2+1,l,r);
	pushup(tree[p].l,tree[p].r,p); 
}
int query_1(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r) return tree[p].sum;
	pushdown(tree[p].l,tree[p].r,p);
	int res=0,mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid) res+=query_1(p*2,l,r);
	if(r>mid) res+=query_1(p*2+1,l,r); 
	return res;
}
int query_2(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r) return tree[p].ans1;
	pushdown(tree[p].l,tree[p].r,p);
	int mid=(tree[p].l+tree[p].r)>>1,longest=0;
	if(l<=mid) longest=max(longest,query_2(p*2,l,r));
	if(r>mid) longest=max(longest,query_2(p*2+1,l,r));
	return longest;
}
//[2,4] [1,3][4,5]->[2,2][3,3][4,4]
//1 1 1 1 1->[1,5]->[1,3][4,5]
//0 0 1 0 0 
//1 1 0 1 1
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	//for(int i=1;i<=n*2;i++) cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].pre0<<" "<<tree[i].pre1<<endl;
	for(int i=1;i<=m;i++){
		int opt,l,r;
		cin>>opt>>l>>r;
		//if(opt==2){
		//	for(int j=1;j<=n*3;j++) cout<<tree[j].l<<" "<<tree[j].r<<" "<<tree[j].sum<<endl;
		//}
		l++,r++;
		if(opt==0) change_0(1,l,r);
		else if(opt==1) change_1(1,l,r);
		else if(opt==2) change_2(1,l,r);
		else if(opt==3) cout<<query_1(1,l,r)<<endl;
		else if(opt==4) cout<<query_2(1,l,r)<<endl;
		//if(opt==0){
			//for(int j=1;j<=n*3;j++) cout<<tree[j].l<<" "<<tree[j].r<<" "<<tree[j].sum<<endl;
		//}
	}
} 
/*
10 3
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
10 4
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
0 3 6
*/

回复

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

正在加载回复...