#include<bits/stdc++.h> #define fru(i,j,k) for(int i=j;i<=k;i++) #define frd(i,j,k) for(int i=j;i>=k;i--) #define pc(x) putchar(x) #define fio(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout); using namespace std; using ll = long long; char c=' '; int in(void) { int x=0;bool f=false; while(!isdigit(c)){f^=c=='-';c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } const int maxn=500012;const int inf=(int)1e9; int n,m,nl[maxn]; int Tp,Wl,Wr,W; struct node { int l,r;ll sum;int mxn,mxh,sm,cnt,tm,tmh,te,teh; }tl[maxn<<2]; inline void pushup(int k) { tl[k].sum=tl[k<<1].sum+tl[k<<1|1].sum; tl[k].mxn=max(tl[k<<1].mxn,tl[k<<1|1].mxn);tl[k].mxh=max(tl[k<<1].mxh,tl[k<<1|1].mxh); if(tl[k<<1].sm>=tl[k<<1|1].mxn) { tl[k].mxn=tl[k<<1].mxn;tl[k].cnt=tl[k<<1].cnt; tl[k].sm=tl[k<<1].sm; } else if(tl[k<<1|1].sm>=tl[k<<1].mxn) { tl[k].mxn=tl[k<<1|1].mxn;tl[k].cnt=tl[k<<1|1].cnt; tl[k].sm=tl[k<<1|1].sm; } else { tl[k].mxn=max(tl[k<<1].mxn,tl[k<<1|1].mxn); if(tl[k<<1].mxn==tl[k<<1|1].mxn) { tl[k].sm=max(tl[k<<1].sm,tl[k<<1|1].sm);tl[k].cnt=tl[k<<1].cnt+tl[k<<1|1].cnt; } else { if(tl[k<<1].mxn<tl[k<<1|1].mxn) { tl[k].sm=tl[k<<1].mxn; tl[k].cnt=tl[k<<1|1].cnt; } else { tl[k].sm=tl[k<<1|1].mxn; tl[k].cnt=tl[k<<1].cnt; } } } } inline void upmx(int k,int w,int wm) { tl[k].tmh=max(tl[k].tmh,tl[k].tm+wm); tl[k].tm+=w; tl[k].sum+=(ll)w*(ll)tl[k].cnt; tl[k].mxh=max(tl[k].mxh,tl[k].mxn+wm); tl[k].mxn+=w; } inline void upe(int k,int w,int wm) { tl[k].teh=max(tl[k].teh,tl[k].te+wm); tl[k].te+=w; tl[k].sum+=(ll)(tl[k].r-tl[k].l+1-tl[k].cnt)*(ll)w; tl[k].sm+=w; } inline void pushdown(int k) { int lmx=tl[k<<1].mxn,rmx=tl[k<<1|1].mxn; if(tl[k].tm||tl[k].tm!=-inf) { if(lmx>rmx)upmx(k<<1,tl[k].tm,tl[k].tmh); else if(lmx<rmx)upmx(k<<1|1,tl[k].tm,tl[k].tmh); else {upmx(k<<1,tl[k].tm,tl[k].tmh);upmx(k<<1|1,tl[k].tm,tl[k].tmh);} tl[k].tm=0;tl[k].tmh=-inf; } if(tl[k].te||tl[k].teh!=-inf) { upe(k<<1,tl[k].te,tl[k].teh);upe(k<<1|1,tl[k].te,tl[k].teh); if(lmx>rmx) { upmx(k<<1|1,tl[k].te,tl[k].teh); } else if(lmx<rmx) { upmx(k<<1,tl[k].te,tl[k].teh); } tl[k].te=0;tl[k].teh=-inf; } } void upmin(int k) { if(W>=tl[k].mxn)return ; if(W>tl[k].sm) { upmx(k,W-tl[k].mxn,W-tl[k].mxn); return ; } pushdown(k); upmin(k<<1);upmin(k<<1|1); pushup(k); } void build(int k,int l,int r) { if(l>r)return ; if(l==r) { tl[k]=(node){l,r,nl[l] ,nl[l],nl[l] ,-inf,1 ,0,-inf,0,-inf}; return ; } int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); tl[k].l=l;tl[k].r=r; pushup(k); } void upd(int k) { if(tl[k].r<Wl||Wr<tl[k].l)return ; if(Wl<=tl[k].l&&tl[k].r<=Wr) { if(Tp==1)upe(k,W,W),upmx(k,W,W); else upmin(k); return ; } pushdown(k); upd(k<<1);upd(k<<1|1); pushup(k); } ll qry(int k) { if(tl[k].r<Wl||Wr<tl[k].l) { if(Tp==3)return 0; else if(Tp==4)return -inf; else return -inf; } if(Wl<=tl[k].l&&tl[k].r<=Wr) { if(Tp==3)return tl[k].sum; else if(Tp==4)return tl[k].mxn; else return tl[k].mxh; } pushdown(k); if(Tp==3)return qry(k<<1)+qry(k<<1|1); else if(Tp==4)return max(qry(k<<1),qry(k<<1|1)); else return max(qry(k<<1),qry(k<<1|1)); } int main() { n=in();m=in(); fru(i,1,n) { nl[i]=in(); } build(1,1,n); while(m--) { Tp=in(); if(Tp<3) { Wl=in();Wr=in();W=in(); upd(1); } else { Wl=in();Wr=in(); printf("%lld\n",qry(1)); } } return 0; }
|