学步园

#include<iostream>
#include<cstdio>
using namespace std;
struct data{
	int l,r,tag,max;
}tr[400000];
int n,m,a[100001];
void build(int k,int s,int t)
{
	tr[k].l=s;tr[k].r=t;
	if(s==t){
		tr[k].max=a[s];
		return;
	}
	int mid=(s+t)>>1;
	build(k<<1,s,mid);build(k<<1|1,mid+1,t);
	tr[k].max=max(tr[k<<1].max,tr[k<<1|1].max);
}
void pushdown(int k)
{
	tr[k<<1].tag+=tr[k].tag;
	tr[k<<1|1].tag+=tr[k].tag;
	tr[k<<1].max+=tr[k].tag;
	tr[k<<1|1].max+=tr[k].tag;
	tr[k].tag=0;
}
void update(int k,int s,int t,int c)
{
	int l=tr[k].l,r=tr[k].r;
	if(l==s&&r==t){
		tr[k].tag+=c;
		tr[k].max+=c;
		return;
	}
	if(tr[k].tag)pushdown(k);
	int mid=(l+r)>>1;
	if(t<=mid)update(k<<1,s,t,c);
	else if(s>mid)update(k<<1|1,s,t,c);
	else{
		update(k<<1,s,mid,c);
		update(k<<1|1,mid+1,t,c);
	}
	tr[k].max=max(tr[k<<1].max,tr[k<<1|1].max);
}
int ask(int k,int s,int t)
{
    int l=tr[k].l,r=tr[k].r;
    if(s==l&&t==r)return tr[k].max;
    if(tr[k].tag)pushdown(k);
    int mid=(l+r)>>1;
    if(t<=mid)return ask(k<<1,s,t);
    else if(s>mid)return ask(k<<1|1,s,t);
    else return max(ask(k<<1,s,mid),ask(k<<1|1,mid+1,t));
 }
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int k,l,r,c;
		scanf("%d",&k);
		if(k==1){
			scanf("%d %d %d",&l,&r,&c);
			update(1,l,r,c);
		}
		else{
			scanf("%d %d",&l,&r);
			printf("%d\n",ask(1,l,r));
		}
	}
	return 0;
}