传送门
线段树好题
支持区间加，区间取min" role="presentation" style="position: relative;">minmin和max" role="presentation" style="position: relative;">maxmax。
维护区间和，区间最大值，区间最小值。
这题可以类比另外一道线段树
维护区间最大，次大，最小，次小，和。
每次修改的时候考虑对每个量产生的影响，然后用最大最小值配合次大次小值剪枝就行了。
注意这题卡空间。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define inf (1<<30)
using namespace std;
inline ll read(){
ll ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
inline void write(ll x){
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar((x%10)^48);
}
int n,m;
ll a[N];
struct Node{int l,r;ll mx,mn,mxx,mnx,cmx,cmn;ll sum,lz;}T[N*3];
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}
inline void pushup(int p){
T[p].sum=T[lc].sum+T[rc].sum;
T[p].mx=max(T[lc].mx,T[rc].mx);
T[p].cmx=(T[p].mx==T[lc].mx?T[lc].cmx:0)+(T[p].mx==T[rc].mx?T[rc].cmx:0);
T[p].mxx=max(T[p].mx==T[lc].mx?T[lc].mxx:T[lc].mx,T[p].mx==T[rc].mx?T[rc].mxx:T[rc].mx);
T[p].mn=min(T[lc].mn,T[rc].mn);
T[p].cmn=(T[p].mn==T[lc].mn?T[lc].cmn:0)+(T[p].mn==T[rc].mn?T[rc].cmn:0);
T[p].mnx=min(T[p].mn==T[lc].mn?T[lc].mnx:T[lc].mn,T[p].mn==T[rc].mn?T[rc].mnx:T[rc].mn);
}
inline void pushnow_mn(int p,ll v){
if(T[p].mn>=v)return;
T[p].sum+=T[p].cmn*(v-T[p].mn);
T[p].mn=v,T[p].mx=max(T[p].mx,v);
if(T[p].mn==T[p].mx)T[p].sum=1ll*(T[p].cmn=T[p].cmx=(T[p].r-T[p].l+1))*(T[p].mx=T[p].mn=v),T[p].mxx=-inf,T[p].mnx=inf;
else T[p].mxx=max(T[p].mxx,v);
}
inline void pushnow_mx(int p,ll v){
if(T[p].mx<=v)return;
T[p].sum+=T[p].cmx*(v-T[p].mx);
T[p].mx=v,T[p].mn=min(T[p].mn,v);
if(T[p].mn==T[p].mx)T[p].sum=1ll*(T[p].cmn=T[p].cmx=(T[p].r-T[p].l+1))*(T[p].mx=T[p].mn=v),T[p].mxx=-inf,T[p].mnx=inf;
else T[p].mnx=min(T[p].mnx,v);
}
inline void pushnow(int p,ll v){
T[p].lz+=v,T[p].sum+=1ll*(T[p].r-T[p].l+1)*v;
T[p].mn+=v,T[p].mx+=v,T[p].mxx+=v,T[p].mnx+=v;
}
inline void pushdown(int p){
if(T[p].lz)pushnow(lc,T[p].lz),pushnow(rc,T[p].lz),T[p].lz=0;
pushnow_mn(lc,T[p].mn),pushnow_mn(rc,T[p].mn);
pushnow_mx(lc,T[p].mx),pushnow_mx(rc,T[p].mx);
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].lz=0;
if(l==r){
T[p].mx=T[p].mn=T[p].sum=a[l];
T[p].cmx=T[p].cmn=1;
T[p].mxx=-inf,T[p].mnx=inf;
return;
}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int ql,int qr,ll v){
if(ql>T[p].r||qr<T[p].l)return;
if(ql<=T[p].l&&T[p].r<=qr){pushnow(p,v);return;}
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline void modify1(int p,int ql,int qr,ll v){
if(ql>T[p].r||qr<T[p].l||T[p].mn>=v)return;
if(ql<=T[p].l&&T[p].r<=qr&&T[p].mnx>v){pushnow_mn(p,v);return;}
pushdown(p);
if(qr<=mid)modify1(lc,ql,qr,v);
else if(ql>mid)modify1(rc,ql,qr,v);
else modify1(lc,ql,mid,v),modify1(rc,mid+1,qr,v);
pushup(p);
}
inline void modify2(int p,int ql,int qr,ll v){
if(ql>T[p].r||qr<T[p].l||T[p].mx<=v)return;
if(ql<=T[p].l&&T[p].r<=qr&&T[p].mxx<v){pushnow_mx(p,v);return;}
pushdown(p);
if(qr<=mid)modify2(lc,ql,qr,v);
else if(ql>mid)modify2(rc,ql,qr,v);
else modify2(lc,ql,mid,v),modify2(rc,mid+1,qr,v);
pushup(p);
}
inline ll query_sum(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
pushdown(p);
if(qr<=mid)return query_sum(lc,ql,qr);
if(ql>mid)return query_sum(rc,ql,qr);
return query_sum(lc,ql,mid)+query_sum(rc,mid+1,qr);
}
inline ll query_max(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return -inf;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx;
pushdown(p);
if(qr<=mid)return query_max(lc,ql,qr);
if(ql>mid)return query_max(rc,ql,qr);
return max(query_max(lc,ql,mid),query_max(rc,mid+1,qr));
}
inline ll query_min(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return inf;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].mn;
pushdown(p);
if(qr<=mid)return query_min(lc,ql,qr);
if(ql>mid)return query_min(rc,ql,qr);
return min(query_min(lc,ql,mid),query_min(rc,mid+1,qr));
}
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
build(1,1,n);
m=read();
while(m--){
int op=read(),l=read(),r=read();
switch(op){
case 1:{ll v=read();update(1,l,r,v);break;}
case 2:{ll v=read();modify1(1,l,r,v);break;}
case 3:{ll v=read();modify2(1,l,r,v);break;}
case 4:{write(query_sum(1,l,r)),puts("");break;}
case 5:{write(query_max(1,l,r)),puts("");break;}
default:{write(query_min(1,l,r)),puts("");break;}
}
}
return 0;
}