萌新求助!线段树先50分后ce不显示原因
查看原帖
萌新求助!线段树先50分后ce不显示原因
318698
Konjac_Wang楼主2021/10/27 19:37

求求大佬了QAQ QAQ QAQ QAQ

推平的tag我也初始化0x3f3f3f了,推平一次我的加tag也都附0了,max我也都初始化成-0x3f3f3f了

样例能过的,可是一传上去洛谷就ce,也不说我ce哪了,就写个编译失败ce报错,ce记录具体我太蒻了不知道洛谷怎么发图链接麻烦大佬看眼我的记录吧orz

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN =500005;
typedef long long ll;
ll n , m , a[MAXN] , tag1[MAXN * 4] , tag2[MAXN*4];
struct tree{
	ll ma = -0x3f3f3f; 
}tree[MAXN*4];
void pushup(ll p){
	tree[p].ma = max(tree[p*2].ma , tree[p*2+1].ma);
}
void movetag(ll p,ll l,ll r,ll d,ll k){
	if(k!=0x3f3f3f)tree[p].ma = k,tag2[p] = k;
	tree[p].ma += d;
	tag1[p] += d;
}             
void pushdown(ll p,ll l,ll r){
	ll mid = (l + r) / 2;
	movetag(2*p,l,mid,tag1[p],tag2[p]);
	movetag(2*p+1,mid+1,r,tag1[p],tag2[p]);
	tag1[p] = 0;tag2[p] = 0x3f3f3f;
}
void build(ll p,ll l,ll r ) {tag2[p] = 0x3f3f3f;
	if(l==r)tree[p].ma = a[l];
	else{
		ll mid = (l+r)/2;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		pushup(p);
	}
}
ll query(ll p,ll l,ll r,ll ql,ll qr){
	if(l>=ql&&r<=qr)return tree[p].ma;
	else{
		pushdown(p,l,r);
		ll mid = (l + r) / 2 , ans = -0x3f3f3f;
		if(ql<=mid)ans = max(ans , query(p*2,l,mid,ql,qr));
		if(qr>mid)ans = max(ans , query(p*2+1,mid+1,r,ql,qr));
		return ans;
	}
} 
void add(ll p,ll l,ll r,ll ql,ll qr ,ll d){
	if(l>=ql&&r<=qr){
		tree[p].ma += d;
		tag1[p] += d;
	}else{
		pushdown(p,l,r);
		ll mid = (l + r) / 2;
		if(ql<=mid)add(p*2,l,mid,ql,qr,d);
		if(mid<qr)add(p*2+1,mid+1,r,ql,qr,d);
		pushup(p);
	}
}
void assign(ll p,ll l,ll r,ll ql,ll qr ,ll d){
	if(l>=ql&&r<=qr){tag1[p] = 0;
		tree[p].ma = d;
		tag2[p] = d;
	}else{
		pushdown(p,l,r);
		ll mid = (l + r) / 2;
		if(ql<=mid)assign(p*2,l,mid,ql,qr,d);
		if(mid<qr)assign(p*2+1,mid+1,r,ql,qr,d);
		pushup(p);
	}
}
int main(){
	cin>>n>>m;
	for(ll i =1;i<=n;++i)cin>>a[i];
	build(1,1,n);
	for(ll i = 1;i<=m;++i){
		ll q , ql, qr , d;
		scanf("%lld%lld%lld",&q,&ql,&qr);
		if(q==1)scanf("%lld",&d) , assign(1,1,n,ql,qr,d);
		if(q==2)scanf("%lld",&d) , add(1,1,n,ql,qr,d);
		if(q==3)printf("%lld\n",query(1,1,n,ql,qr));
	}
	return 0;
} 
2021/10/27 19:37
加载中...