蒟蒻50pts求助 点6~10WA
查看原帖
蒟蒻50pts求助 点6~10WA
408649
MathCalculus楼主2023/8/31 20:27

query里面INF感觉调够大了QwQ,有没有大佬帮帮我

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000005],w[1000005*4];
ll add[1000005*4],mod[1000005*4];
bool is_mod[1000005*4];//是否修改过

bool inRange(int L,int R,int l,int r){
	return (L>=l) && (R<=r);
}
bool outRange(int L,int R,int l,int r){
	return (L>r) || (R<l);
}
void pushup(int u){
	w[u] = max(w[u*2],w[u*2+1]);
}
void maketag(int u,int val,int type){
	if(type==1){//modify
		add[u] = 0;
		mod[u] = val;
		is_mod[u] = true;
		w[u] = val;
	}else{//add
		if(is_mod[u]){
			mod[u] += val;
		}else{
			add[u] += val;
		}
		w[u] += val;
	}
}
void pushdown(int u){
	if(is_mod[u]){
		maketag(u*2,mod[u],1);
		maketag(u*2+1,mod[u],1);
		add[u] = 0;
		is_mod[u] = 0;
		mod[u] = 0;
	}else{
		maketag(u*2,add[u],2);
		maketag(u*2+1,add[u],2);
		add[u] = 0;
	}
}
void build(int u,int L,int R){
	if(L==R){
		w[u]=a[L];
	}else{
		int mid = (L+R)/2;
		build(u*2,L,mid);
		build(u*2+1,mid+1,R);
		pushup(u);
	}
}
ll query(int u,int L,int R,int l,int r){
	//printf("query %d %d %d %d %d ",u,L,R,l,r);
	if(inRange(L,R,l,r)){
		return w[u];
	}else if(!outRange(L,R,l,r)){
		pushdown(u);
		int mid = (L+R)/2;
		return max(query(u*2,L,mid,l,r),query(u*2+1,mid+1,R,l,r));
	}
	return -0x7fffffffffffffff;
}
void update(int u,int L,int R,int l,int r,int val,int type){
	if(inRange(L,R,l,r)){
		maketag(u,val,type);
	}else if(!outRange(L,R,l,r)){
		int mid = (L+R)/2;
		pushdown(u);
		update(u*2,L,mid,l,r,val,type);
		update(u*2+1,mid+1,R,l,r,val,type);
		pushup(u);
	}
}

int main(){
	int n,q;
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int op,l,r,x;
		scanf("%d",&op);
		if(op==1){
			scanf("%d %d %d",&l,&r,&x);
            l=min(l,r);r=max(l,r);
			update(1,1,n,l,r,x,1);
		}else if(op==2){
			scanf("%d %d %d",&l,&r,&x);
            l=min(l,r);r=max(l,r);
			update(1,1,n,l,r,x,2);
		}else{
			scanf("%d %d",&l,&r);
            l=min(l,r);r=max(l,r);
			printf("%lld\n",query(1,1,n,l,r));
		}
	}
}
2023/8/31 20:27
加载中...