50分求调

rt

#include <bits/stdc++.h>
using namespace std;
const int N=1000000;
struct node
{
 long long change_tag;
 long long add_tag;
 long long maxn;
 bool flag;
};
node tree[4*N+5];
long long x[N+5];
void built(int p,int l,int r)
{
 if(l==r)
 {
    tree[p].change_tag=0;
    tree[p].flag=false;
    tree[p].maxn=x[l];
    tree[p].add_tag=0;
    return ;
 }
 int mid=(l+r)/2;
 built(p*2,l,mid);
 built(p*2+1,mid+1,r);
 tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
 tree[p].change_tag=0;
 tree[p].flag=false;
 tree[p].add_tag=0;
}
void pushdown(int p,int l,int r)
{
 if(tree[p].flag!=false)
 {
    tree[p*2+1].flag=true;
    tree[p*2+1].add_tag=0;
    tree[p*2+1].maxn=tree[p].change_tag;
    tree[p*2+1].change_tag=tree[p].change_tag;
    tree[p*2].flag=true;
    tree[p*2].add_tag=0;
    tree[p*2].maxn=tree[p].change_tag;
    tree[p*2].change_tag=tree[p].change_tag;
    tree[p].change_tag=0;
    tree[p].flag=false;
 }
 if(tree[p].add_tag)
 {
    tree[p*2+1].add_tag+=tree[p].add_tag;
    tree[p*2+1].maxn+=tree[p].add_tag;
    tree[p*2].add_tag+=tree[p].add_tag;
    tree[p*2].maxn+=tree[p].add_tag;
    tree[p].add_tag=0;
 }
}
void change(int L,int R,int p,int l,int r,int d)
{
 if(L<=l&&R>=r)
 {
    tree[p].maxn=d;
    tree[p].add_tag=0;
    tree[p].change_tag=d;
    tree[p].flag=true;
    return ;
 }
 int mid=(l+r)/2;
 pushdown(p,l,r);
 if(L<=mid) change(L,R,p*2,l,mid,d);
 if(R>mid)  change(L,R,p*2+1,mid+1,r,d);
 tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
void add_change(int L,int R,int p,int l,int r,int d)
{
 if(L<=l&&R>=r)
 {
    tree[p].maxn+=d;
    tree[p].add_tag+=d;
    return ;
 }
 int mid=(l+r)/2;
 pushdown(p,l,r);
 if(L<=mid) add_change(L,R,p*2,l,mid,d);
 if(R>mid)  add_change(L,R,p*2+1,mid+1,r,d);
 tree[p].maxn=max(tree[p*2].maxn,tree[p*2+1].maxn);
}
long long search(int L,int R,int p,int l,int r)
{
 if(L<=l&&R>=r)
    return tree[p].maxn;
 long long res=-1e9;
 int mid=(l+r)/2;
 pushdown(p,l,r);
 if(L<=mid) res=max(search(L,R,p*2,l,mid),res);
 if(R>mid)  res=max(search(L,R,p*2+1,mid+1,r),res);
 return res;
}
int main()
{
 int m,n;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
    scanf("%lld",&x[i]);
 built(1,1,n);
 while(m--)
 {
    int a1,a2,a3,a4;
    scanf("%d",&a1);
    if(a1==1)
    {
        scanf("%d%d%d",&a2,&a3,&a4);
        change(a2,a3,1,1,n,a4);
    }
    if(a1==2)
    {
        scanf("%d%d%d",&a2,&a3,&a4);
        add_change(a2,a3,1,1,n,a4);
    }
    if(a1==3)
    {
        scanf("%d%d",&a2,&a3);
        printf("%lld\n",search(a2,a3,1,1,n));
    }
 }
 return 0;
}