《Segment tree Beats!》，反正我不会
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=4e5+;
const ll inf=1e15+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} ll a[maxn];
int N,M;
ll sum[maxn<<],mn[maxn<<][],se[maxn<<],laz[maxn<<]; inline void update(int p){
sum[p]=sum[p<<]+sum[p<<|];
if(mn[p<<][]==mn[p<<|][]){
mn[p][]=mn[p<<][],mn[p][]=mn[p<<][]+mn[p<<|][];
se[p]=min(se[p<<],se[p<<|]);
}
else if(mn[p<<][]<mn[p<<|][]){
mn[p][]=mn[p<<][],mn[p][]=mn[p<<][];
se[p]=min(se[p<<],mn[p<<|][]);
}
else if(mn[p<<][]>mn[p<<|][]){
mn[p][]=mn[p<<|][],mn[p][]=mn[p<<|][];
se[p]=min(se[p<<|],mn[p<<][]);
}
} void pushdown(int p){
if(!laz[p]) return;
ll x=laz[p];laz[p]=;
if(x<=mn[p][]) return;
laz[p<<]=max(x,laz[p<<]);
laz[p<<|]=max(x,laz[p<<|]);
if(x<se[p]){
sum[p]+=mn[p][]*(x-mn[p][]);
mn[p][]=x;
return;
}
pushdown(p<<);pushdown(p<<|);
update(p); } void change(int p,int l,int r,int x,int y,ll z){
if(x<=l&&r<=y){
laz[p]=max(laz[p],z);
pushdown(p);
}
else{
pushdown(p);
int m=l+r>>;
if(x<=m) change(p<<,l,m,x,y,z);
else pushdown(p<<);
if(y>=m+) change(p<<|,m+,r,x,y,z);
else pushdown(p<<|);
update(p);
}
} void build(int p,int l,int r){
if(l==r){
mn[p][]=sum[p]=a[l];
mn[p][]=,se[p]=inf;
}else{
int m=l+r>>;
build(p<<,l,m);build(p<<|,m+,r);
update(p);
}
} ll query(int p,int l,int r,int x,int y){
pushdown(p);
if(x<=l&&r<=y) return sum[p];
int m=l+r>>;ll re=;
if(x<=m) re=query(p<<,l,m,x,y);
if(y>=m+) re+=query(p<<|,m+,r,x,y);
return re;
} int main(){
//freopen("","r",stdin);
int i;
N=rd(),M=rd();
for(i=;i<=N;i++)
a[i]=rd();
build(,,N);
for(i=;i<=M;i++){
ll a=rd(),b=rd(),c=rd();
if(!a) printf("%lld\n",query(,,N,b,c));
else change(,,N,b,c,a);
}
return ;
}