50pts线段树求条

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;

#define int long long
#define maxn 1000005
#define none -1145141919180

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int n,q;
int val[maxn];
int sum[maxn];
int clr[maxn];
int www[maxn];
int nowl,nowr;
int opt;

void update(int rt){
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
    return;
}//更新（建树）

void build(int l,int r,int rt){
    if(l==r){
        sum[rt]=val[l];
        www[rt]=none;
        clr[rt]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    update(rt);
}//建树

void color1(int l,int r,int rt,int val){
    clr[rt]=0;
    www[rt]=val+clr[rt];
    sum[rt]=www[rt];
    return;
}//opt 1 的标记

void push_color1(int l,int r,int rt){
    if(www[rt]!=none){
        int mid=(l+r)>>1;
        color1(l,mid,rt<<1,www[rt]);
        color1(mid+1,r,rt<<1|1,www[rt]);
        www[rt]=none;
    }
    return;
}//下放标记

void change1(int l,int r,int rt,int x){
    if(l>=nowl&&r<=nowr){
        color1(l,r,rt,x);
        return;
    }
    push_color1(l,r,rt);
    int mid=(l+r)>>1;
    if(mid>=nowl) change1(l,mid,rt<<1,x);
    if(mid+1<=nowr) change1(mid+1,r,rt<<1|1,x);
    update(rt);
    return;
}//opt1 操作

void color2(int l,int r,int rt,int c){
    sum[rt]=sum[rt]+c;
    clr[rt]+=c;
    return; 
}//opt 2 标记

void push_color2(int l,int r,int rt){
    if(clr[rt]){
        int mid=(l+r)>>1;
        color2(l,mid,rt<<1,clr[rt]);
        color2(mid+1,r,rt<<1|1,clr[rt]);
        clr[rt]=0;
    }
    return;
}//下放

void change2(int l,int r,int rt,int x){
    if(l>=nowl&&r<=nowr){
        color2(l,r,rt,x);
        return;
    }
    push_color2(l,r,rt);
    int mid=(l+r)>>1;
    if(mid>=nowl) change2(l,mid,rt<<1,x);
    if(mid+1<=nowr) change2(mid+1,r,rt<<1|1,x);
    update(rt);
    return;
}//更改 opt 2

int find(int l,int r,int rt){
    int ans=-1;
    if(l>=nowl&&r<=nowr){
        return sum[rt];
    }
    int mid=(l+r)>>1;
    push_color2(l,r,rt);
    push_color2(l,r,rt);
    if(mid>=nowl){
        int fff=find(l,mid,rt<<1); 
        ans=max(fff,ans);
    }
    if(mid+1<=nowr){
        int fff=find(mid+1,r,rt<<1|1); 
        ans=max(fff,ans);
    }
    return ans;
}//查询

signed main(){
    n=read();q=read();
    for(int i=1;i<=n;++i){
        val[i]=read();
    }
    build(1,n,1);
    for(int i=1;i<=q;++i){
        opt=read();
        if(opt==1){
            int x;
            nowl=read();nowr=read();x=read();
            change1(1,n,1,x);
        }
        else if(opt==2){
            int x;
            nowl=read();nowr=read();x=read();
            change2(1,n,1,x);
        }
        else{
            nowl=read();nowr=read();
            cout<<find(1,n,1)<<endl;
        }
    }
    return 0;
}