社区讨论

How G?

学术版参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mkiddrdh
此快照首次捕获于
2026/01/17 21:55
上个月
此快照最后确认于
2026/01/20 23:55
4 周前
查看原帖
rt,我的思路:维护区间状态(0:全反,1:全正,2:部分)+区间max
关键代码:
CPP
void pushdown(int i){
	if(tr[i].lazy1){
		if(tr[2*i].fm!=0){
			tr[2*i].lazy1+=tr[i].lazy1;
			tr[2*i].maxx+=tr[i].lazy1;
		}
		if(tr[2*i+1].fm!=0){
			tr[2*i+1].lazy1+=tr[i].lazy1;
			tr[2*i+1].maxx+=tr[i].lazy1;
		}
		tr[i].lazy1=0;
	}
	if(tr[i].lazy2){
		tr[2*i].maxx=0;
		tr[2*i+1].maxx=0;
		tr[2*i].lazy2=tr[i].lazy2;
		tr[2*i+1].lazy2=tr[i].lazy2;
		if(tr[2*i].fm!=2){
			tr[2*i].fm^=1;
		}
		if(tr[2*i+1].fm!=2){
			tr[2*i+1].fm^=1;
		}
		tr[i].lazy2=0;
	}
}
void pushup(int i){
	tr[i].maxx=max(tr[2*i].maxx,tr[2*i+1].maxx);
	if(tr[2*i].fm==0 && tr[2*i+1].fm==0) tr[i].fm=0;
	else if(tr[2*i].fm==1 && tr[2*i+1].fm==1) tr[i].fm=1;
	else tr[i].fm=2;
}
代码:
CPP
#include<iostream>
#define int long long
using namespace std;
int n,q;
int t,l,r,x;
const int N=2e5+5;
struct Node{
	int l,r;
	int maxx;
	int fm;
	int lazy1,lazy2;
}tr[4*N];
void pushdown(int i){
	if(tr[i].lazy1){
		if(tr[2*i].fm!=0){
			tr[2*i].lazy1+=tr[i].lazy1;
			tr[2*i].maxx+=tr[i].lazy1;
		}
		if(tr[2*i+1].fm!=0){
			tr[2*i+1].lazy1+=tr[i].lazy1;
			tr[2*i+1].maxx+=tr[i].lazy1;
		}
		tr[i].lazy1=0;
	}
	if(tr[i].lazy2){
		tr[2*i].maxx=0;
		tr[2*i+1].maxx=0;
		tr[2*i].lazy2=tr[i].lazy2;
		tr[2*i+1].lazy2=tr[i].lazy2;
		if(tr[2*i].fm!=2){
			tr[2*i].fm^=1;
		}
		if(tr[2*i+1].fm!=2){
			tr[2*i+1].fm^=1;
		}
		tr[i].lazy2=0;
	}
}
void pushup(int i){
	tr[i].maxx=max(tr[2*i].maxx,tr[2*i+1].maxx);
	if(tr[2*i].fm==0 && tr[2*i+1].fm==0) tr[i].fm=0;
	else if(tr[2*i].fm==1 && tr[2*i+1].fm==1) tr[i].fm=1;
	else tr[i].fm=2;
}
void build(int i,int l,int r){
//	cout<<1<<endl;
	tr[i]={l,r};
	if(l==r){
		tr[i].maxx=0;
		tr[i].fm=1;
		return;
	}
	int mid=(l+r)>>1;
	build(2*i,l,mid);
	build(2*i+1,mid+1,r);
	pushup(i);
}
void modify1(int i,int l,int r,int k){
	if(l<=tr[i].l && tr[i].r<=r){
		tr[i].maxx+=k;
		tr[i].lazy1+=k;
		return;
	}
	if(l>tr[i].r or r<tr[i].l){
		return;
	}
	pushdown(i);
	modify1(2*i,l,r,k);
	modify1(2*i+1,l,r,k);
	pushup(i);
}
void modify2(int i,int l,int r){
	if(l<=tr[i].l && tr[i].r<=r){
		tr[i].maxx=0;
		if(tr[i].fm!=2){
			tr[i].fm^=1;
		}
		tr[i].lazy2=1;
		return;
	}
	if(l>tr[i].r or r<tr[i].l){
		return;
	}
	pushdown(i);
	modify2(2*i,l,r);
	modify2(2*i+1,l,r);
	pushup(i);
}
int query(int i,int l,int r){
	if(l<=tr[i].l && tr[i].r<=r){
		return tr[i].maxx;
	}
	if(l>tr[i].r or r<tr[i].l){
		return 0;
	}
	pushdown(i);
	int res=0;
	res=max(res,query(2*i,l,r));
	res=max(res,query(2*i+1,l,r));
	return res;
}
signed main(){
	cin>>n>>q;
	build(1,1,n);
	for(int i=1;i<=q;i++){
		cin>>t;
		if(t==1){
			cin>>l>>r>>x;
			modify1(1,l,r,x);
		}
		else if(t==2){
			cin>>l>>r;
			modify2(1,l,r);
		}
		else{
			cin>>l>>r;
			cout<<query(1,l,r)<<endl;
		}
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...