线段树萌新50分,秋眺QWQ
查看原帖
线段树萌新50分,秋眺QWQ
1123553
CMiBold楼主2024/11/20 23:38

调了1个小时没调出来,嘛回事啊,还是求各位大佬帮忙求调,谢谢了。


#include<bits/stdc++.h>
using namespace std;
#define luo_xing main
#define pb push_back
typedef long long ll;
const int N=1e6+10;
ll q,n,op;
ll f[N*4],tag[N*4],xiu[N*4]; 
ll xy[N*4];
void build(ll k,ll l,ll r){
	if(l==r){
		cin>>f[k];	
		return;
	}
	ll mid=(l+r)>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	f[k]=max(f[k*2],f[k*2+1]);
	return;
}
void put_xiu(ll k){
	if(xy[k]){
		xiu[k*2]=xiu[k];
		xiu[k*2+1]=xiu[k];
		f[k*2]=xiu[k];
		f[k*2+1]=xiu[k];
		xy[k*2]=1;
		xy[k*2+1]=1;
		xy[k]=0;
		tag[k*2+1]=0;
		tag[k*2]=0;
	}
	return;
}
void put_tag(ll k){
//	cout<<"tag:"<<tag[k*2]<<" "<<tag[k*2+1]<<" "<<tag[k]<<" "<<k<<endl;
	tag[k*2]+=tag[k];
	tag[k*2+1]+=tag[k];
	f[k*2]+=tag[k];
	f[k*2+1]+=tag[k];
	tag[k]=0;
	return;
}
void xchange(ll k,ll l,ll r,ll x,ll y,ll v){
	if(l>y || r<x) return;
	if(l>=x && r<=y){
		f[k]=v;
		xy[k]=1;
		xiu[k]=v;
		tag[k]=0;
		return;
	}
	ll mid=(l+r)>>1;
	put_xiu(k);
	put_tag(k);
	xchange(k*2,l,mid,x,y,v);
	xchange(k*2+1,mid+1,r,x,y,v);
	f[k]=max(f[k*2],f[k*2+1]);
	return;
}
void jchange(ll k,ll l,ll r,ll x,ll y,ll v){
	if(l>y || r<x) return;
	if(l>=x && r<=y){
		if(xy[k]) xiu[k]+=v;
		f[k]+=v;
		tag[k]+=v;
		return;
	}
	ll mid=(l+r)>>1;
	put_xiu(k);
	put_tag(k);
	jchange(k*2,l,mid,x,y,v);
	jchange(k*2+1,mid+1,r,x,y,v);
	f[k]=max(f[k*2],f[k*2+1]);
	return;
}
ll ask(ll k,ll l,ll r,ll x,ll y){
	if(l>y || r<x) return -INT_MAX;
	if(l>=x && r<=y){
		if(xy[k]) return xiu[k];
		return f[k];
	}
	ll mid=(l+r)>>1;
	put_xiu(k);
	put_tag(k);
	ll ma=0;
	ma=max(ask(k*2,l,mid,x,y),ask(k*2+1,mid+1,r,x,y));
	return ma;
}
int luo_xing(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	build(1,1,n);
	ll l,r,x;
	while(q--){
		cin>>op>>l>>r;
		if(op==1){
			cin>>x;
			xchange(1,1,n,l,r,x);
		}else if(op==2){
			cin>>x;
			jchange(1,1,n,l,r,x);
		}else{
			cout<<ask(1,1,n,l,r)<<'\n';
		}
	}
	return 0;
}

QWQ

2024/11/20 23:38
加载中...