题目P1253 扶苏的问题

记录

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define lc p << 1
#define rc p << 1 | 1

typedef long long ll;
const ll N=1000010, inf=-(1e18+10);
ll a[N];

struct tree{
	ll l, r, sum, add, ch;
}t[4*N];

void pushup(ll p){
	t[p].sum=max(t[lc].sum,t[rc].sum);
}

void pushdown(ll p){
	if(t[p].ch==inf){
		t[lc].sum+=t[p].add;
		t[rc].sum+=t[p].add;
		t[lc].add+=t[p].add;
		t[rc].add+=t[p].add;
	}else{
		t[lc].sum=t[rc].sum=t[p].ch+t[p].add;
		t[lc].ch=t[rc].ch=t[p].ch+t[p].add;
		t[lc].add=t[lc].add=0;
	}
	t[p].ch=inf;																									
	t[p].add=0;
}

void built(ll p, ll l, ll r){
	t[p]=tree{l, r, a[l], 0, inf};
	if(l==r) return ;
	ll mid=(l+r) >> 1;
	built(lc, l, mid);
	built(rc, mid+1, r);
	pushup(p);
}

void update(ll p, ll x, ll y, ll k){
	if(t[p].l>y || t[p].r<x) return ;
	if(x<=t[p].l && t[p].r<=y){
		t[p].add=0;
		t[p].ch=k;
		t[p].sum=k;
		return ;
	}
	pushdown(p);
	update(lc, x, y, k);
	update(rc, x, y, k);
	pushup(p);
}

void update2(ll p, ll x, ll y, ll k){
	if(t[p].l>y || t[p].r<x) return ;
	if(x<=t[p].l && t[p].r<=y){
		t[p].sum+=k;
		t[p].add+=k;
		return ;
	}
	pushdown(p);
	update2(lc, x, y, k);
	update2(rc, x, y, k);
	pushup(p);
}

ll query(ll p, ll x, ll y){
	if(y<t[p].l || t[p].r<x) return inf;
	if(t[p].l>=x && t[p].r<=y) return t[p].sum;
	pushdown(p);
	return max(query(lc, x, y), query(rc, x, y));
}

int main(){
	
	ll n, m, op, l, r, x;
	scanf("%lld%lld", &n, &m);
	for(ll i=1; i<=n; i++) scanf("%lld", &a[i]);
	built(1, 1, n);
	for(ll i=1; i<=m; i++){
		scanf("%lld%lld%lld", &op, &l, &r);
		if(op==1){
			scanf("%lld", &x);
			update(1, l, r, x);
		}
		if(op==2){
			scanf("%lld", &x);
			update2(1, l, r, x);
		}
		if(op==3){
			printf("%lld\n", query(1, l, r));
		}
	}
	
	return 0;
}