---
tags: codebook
---

# segment tree beats

https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define endl '\n'
using namespace std;
using ll=long long;
template<typename T> using V=vector<T>;
constexpr int maxn=200005;
constexpr ll infll=0x3f3f3f3f3f3f3f3f;
struct node{
    ll sum,inc,mx,smx,cmx,tmn,mn,smn,cmn,tmx;
    node(ll x=0):sum(x),inc(0),mx(x),smx(-infll),cmx(1),tmn(infll),
        mn(x),smn(infll),cmn(1),tmx(-infll){}
    void pull(int,int);
} arr[(maxn+1)<<2];
#define m ((l+r)>>1)
void node::pull(int l,int r){
    sum=cmx=cmn=0,mx=smx=-infll,mn=smn=infll;
    for(auto i:{l,r}){
        sum+=arr[i].sum;
        mx=max(mx,arr[i].mx);
        mn=min(mn,arr[i].mn);
    }
    for(auto i:{l,r}){
        if(arr[i].mx==mx)
            cmx+=arr[i].cmx;
        if(arr[i].mn==mn)
            cmn+=arr[i].cmn;
        if(arr[i].mn>mn)
            smn=min(smn,arr[i].mn);
        if(arr[i].smn>mn)
            smn=min(smn,arr[i].smn);
        if(arr[i].mx<mx)
            smx=max(smx,arr[i].mx);
        if(arr[i].smx<mx)
            smx=max(smx,arr[i].smx);
    }
}
void build(V<ll>& v,int i=1,int l=0,int r=maxn){
    if((int)v.size()<=l) return;
    if(r-l==1){arr[i]=v[l];return;}
    build(v,i<<1,l,m),build(v,i<<1|1,m,r);
    arr[i].pull(i<<1,i<<1|1);
}
inline void pushinc(int i,ll k,int l,int r){
    arr[i].sum+=(r-l)*k;
    arr[i].mx+=k,arr[i].mn+=k;
    if(arr[i].smx!=-infll) arr[i].smx+=k;
    if(arr[i].smn!=infll) arr[i].smn+=k;
    if(arr[i].tmx!=infll) arr[i].tmx+=k;
    if(arr[i].tmn!=infll) arr[i].tmn+=k;
    arr[i].inc+=k;
}
inline void pushmin(int i,ll k){
    if(arr[i].mx<=k) return;
    arr[i].sum+=(k-arr[i].mx)*arr[i].cmx;
    if(arr[i].smn==arr[i].mx) arr[i].smn=k;
    if(arr[i].mn==arr[i].mx) arr[i].mn=k;
    if(arr[i].tmx>k) arr[i].tmx=k;
    arr[i].mx=k,arr[i].tmn=k;
}
inline void pushmax(int i,ll k){
    if(arr[i].mn>=k) return;
    arr[i].sum+=(k-arr[i].mn)*arr[i].cmn;
    if(arr[i].smx==arr[i].mn) arr[i].smx=k;
    if(arr[i].mx==arr[i].mn) arr[i].mx=k;
    if(arr[i].tmn<k) arr[i].tmn=k;
    arr[i].mn=k,arr[i].tmx=k;
}
inline void push(int i,int l,int r){
    if(arr[i].inc)
        pushinc(i<<1,arr[i].inc,l,m),pushinc(i<<1|1,arr[i].inc,m,r);
    if(arr[i].tmx!=-infll) pushmax(i<<1,arr[i].tmx),pushmax(i<<1|1,arr[i].tmx);
    if(arr[i].tmn!=infll) pushmin(i<<1,arr[i].tmn),pushmin(i<<1|1,arr[i].tmn);
    arr[i].inc=0,arr[i].tmx=-infll,arr[i].tmn=infll;
}
void increase(int ql,int qr,ll k,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return;
    if(ql<=l&&r<=qr) return pushinc(i,k,l,r);
    push(i,l,r);
    increase(ql,qr,k,i<<1,l,m),increase(ql,qr,k,i<<1|1,m,r);
    arr[i].pull(i<<1,i<<1|1);
}
void tomin(int ql,int qr,ll k,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql||arr[i].mx<=k) return;
    if(ql<=l&&r<=qr&&arr[i].smx<k) return pushmin(i,k);
    push(i,l,r);
    tomin(ql,qr,k,i<<1,l,m),tomin(ql,qr,k,i<<1|1,m,r);
    arr[i].pull(i<<1,i<<1|1); 
}
void tomax(int ql,int qr,ll k,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql||arr[i].mn>=k) return;
    if(ql<=l&&r<=qr&&arr[i].smn>k) return pushmax(i,k);
    push(i,l,r);
    tomax(ql,qr,k,i<<1,l,m),tomax(ql,qr,k,i<<1|1,m,r);
    arr[i].pull(i<<1,i<<1|1);
}
ll query(int ql,int qr,int i=1,int l=0,int r=maxn){
    if(qr<=l||r<=ql) return 0;
    if(ql<=l&&r<=qr) return arr[i].sum;
    push(i,l,r);
    return query(ql,qr,i<<1,l,m)+query(ql,qr,i<<1|1,m,r);
}
#undef m
inline void solve(){
    int n,q;cin>>n>>q;
    V<ll> v(n);
    for(auto& i:v)
        cin>>i;
    build(v);
    while(q--){
        int op,ql,qr;cin>>op;
        ll k;
        switch(op){
        case 0:{
            cin>>ql>>qr>>k;
            tomin(ql,qr,k);
        }break;
        case 1:{
            cin>>ql>>qr>>k;
            tomax(ql,qr,k);
        }break;
        case 2:{
            cin>>ql>>qr>>k;
            increase(ql,qr,k);
        }break;
        case 3:{
            cin>>ql>>qr;
            cout<<query(ql,qr)<<endl;
        }break;
        }
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}