T40 求调

rt

#include <cstring>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <limits.h>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <time.h>
#include <random>
using namespace std;
#define min(a,b) ((a)>(b)?(b):(a))
#define max(a,b) ((a)<(b)?(b):(a))
#define INF 1e18
#define ll long long
#define sc scanf
#define pr printf
#define v1 first
#define v2 second
#define f(nm1,nm2,nm3) for(int nm1=nm2; nm1<= nm3; nm1++)
#define lowbit(x) (x&(-x))
int a[1000006];
//segment tree
#define lson k*2,l,mid
#define rson k*2+1,mid+1,r
#define mid ((l+r)>>1)

struct node{
    ll val,lazy1,lazy2;
}e[4000005];
void merge(node &k,node ls,node rs)
{
    k.val=max(ls.val,rs.val);
}
void build(int k,int l,int r)
{
    e[k].lazy1=INF;
    e[k].lazy2=0;
    if(l==r)
    {
        e[k].val=a[l];
        return;
    }
    build(lson);
    build(rson);
    if(l!=r)
    merge(e[k],e[k*2],e[k*2+1]);
}
void push_down(node &k, node &ls,node &rs)
{
    if(k.lazy1!=INF){
        ls.val=k.lazy1;
        rs.val=k.lazy1;
        ls.lazy1=rs.lazy1=k.lazy1;
        ls.lazy2=rs.lazy2=0;
        k.lazy1=INF;
    }
    ls.val+=k.lazy2;
    rs.val+=k.lazy2;
    ls.lazy2+=k.lazy2;
    rs.lazy2+=k.lazy2;
    k.lazy2=0;
}
void modify1(int k,int l,int r,const int lbor,const int rbor,const ll val)
{
    if(lbor<=l&&r<=rbor)
    {
        e[k].val=val;
        e[k].lazy1=val;
        e[k].lazy2=0;
        return;
    }
    push_down(e[k],e[k*2],e[k*2+1]);
    if(mid>=lbor)
    {
        modify1(lson,lbor,rbor,val);
    }
    if(mid<rbor)
    {
        modify1(rson,lbor,rbor,val);
    }
    merge(e[k],e[k*2],e[k*2+1]);
}
void modify2(int k,int l,int r,const int lbor,const int rbor,const ll val)
{
    if(lbor<=l&&r<=rbor)
    {
        e[k].val+=val;
        e[k].lazy2+=val;
        return;
    }
    push_down(e[k],e[k*2],e[k*2+1]);
    if(mid>=lbor)
    {
        modify2(lson,lbor,rbor,val);
    }
    if(mid<rbor)
    {
        modify2(rson,lbor,rbor,val);
    }
    merge(e[k],e[k*2],e[k*2+1]);
}
ll query(int k,int l,int r,const int lbor,const int rbor)
{
    if(lbor<=l&&r<=rbor)
    {
        return e[k].val;
    }
    push_down(e[k],e[k*2],e[k*2+1]);
    ll ans=-INF;
    if(mid>=lbor)
    {
        ans=max(ans,query(lson,lbor,rbor));
    }
    if(mid<rbor)
    {
        ans=max(ans,query(rson,lbor,rbor));
    }
    return ans;
}
#undef lson
#undef rson
#undef mid
//end segment tree
#undef int
int n,q;
signed main()
{
//    freopen("/Users/wj/Downloads/P1253_2.in","r",stdin);
    sc("%d%d",&n,&q);
    for(int i=1; i <= n; i++)
    {
        sc("%d",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        int op;
        sc("%d",&op);
        if(op==1)
        {
            int l,r;
            ll x;
            sc("%d%d%lld",&l,&r,&x);
            modify1(1,1,n,l,r,x);
        }
        else if(op==2)
        {
            int l,r;
            ll x;
            sc("%d%d%lld",&l,&r,&x);
            modify2(1,1,n,l,r,x);
        }
        else{
            int l,r;
            sc("%d%d",&l,&r);
            pr("%lld\n",query(1,1,n,l,r));
        }
    }
    return 0;
}