https://www.luogu.com.cn/record/201437211

#include<bits/stdc++.h>
using namespace std;
namespace seg_tree{
	#define ll long long
	const int N=5e5+10;
	const int INF=2e9;
	int ra[N];
	struct seg_node{
		int maxf,maxs,maxc,maxt;
		int minf,mins,minc,mint;
		int addt;
		ll sum;
	}a[N<<2];
	
	void pushu(int p){
		const int ls=p<<1,rs=p<<1|1;
		a[p].sum=a[ls].sum+a[rs].sum;
		if(a[ls].maxf==a[rs].maxf){
			a[p].maxf=a[ls].maxf;
			a[p].maxc=a[ls].maxc+a[rs].maxc;
			a[p].maxs=max(a[ls].maxs,a[rs].maxs);
		}else if(a[ls].maxf>a[rs].maxf){
			a[p].maxf=a[ls].maxf;
			a[p].maxc=a[ls].maxc;
			a[p].maxs=max(a[ls].maxs,a[rs].maxf);			
		}else{
			a[p].maxf=a[rs].maxf;
			a[p].maxc=a[rs].maxc;
			a[p].maxs=max(a[ls].maxf,a[rs].maxs);
		}
		if(a[ls].minf==a[rs].minf){
			a[p].minf=a[ls].minf;
			a[p].minc=a[ls].minc+a[rs].minc;
			a[p].mins=min(a[ls].mins,a[rs].mins);
		}else if(a[ls].minf<a[rs].minf){
			a[p].minf=a[ls].minf;
			a[p].minc=a[ls].minc;
			a[p].mins=min(a[ls].mins,a[rs].minf);			
		}else{
			a[p].minf=a[rs].minf;
			a[p].minc=a[rs].minc;
			a[p].mins=min(a[ls].minf,a[rs].mins);
		}
	}
	
	void paddt(int p,int l,int r,int val){
		a[p].sum+=(ll)(r-l+1ll)*val;
		a[p].maxf+=val;
		a[p].minf+=val;
		if(a[p].maxs!=-INF)a[p].maxs+=val;
		if(a[p].mins!= INF)a[p].mins+=val;
		if(a[p].maxt!=-INF)a[p].maxt+=val;
		if(a[p].mint!= INF)a[p].mint+=val;
		a[p].addt+=val;
	}
	void pmint(int p,int val){
		if(a[p].maxf<=val)return;
		a[p].sum+=(ll)(val*1ll-a[p].maxf)*a[p].maxc;
		if(a[p].mins==a[p].maxf)a[p].mins=val;
		if(a[p].minf==a[p].maxf)a[p].minf=val;
		if(a[p].maxt>val)a[p].maxt=val;
		a[p].maxf=val;
		a[p].mint=val;
	}
	void pmaxt(int p,int val){
		if(a[p].maxf>val)return;
		a[p].sum+=(ll)(val*1ll-a[p].minf)*a[p].minc;
		if(a[p].maxs==a[p].minf)a[p].maxs=val;
		if(a[p].maxf==a[p].minf)a[p].maxf=val;
		if(a[p].mint<val)a[p].mint=val;
		a[p].minf=val;
		a[p].maxt=val;		
	} 
	
	void pushd(int p,int l,int r){
		const int ls=p<<1,rs=p<<1|1,mi=(l+r)>>1;
		if(a[p].addt){
			paddt(ls,l,mi,  a[p].addt);
			paddt(rs,mi+1,r,a[p].addt);
			a[p].addt=0;
		}
		if(a[p].maxt!=-INF){
			pmaxt(ls,a[p].maxt);
			pmaxt(rs,a[p].maxt);
			a[p].maxt=-INF;
		}
		if(a[p].mint!= INF){
			pmint(ls,a[p].mint);
			pmint(rs,a[p].mint);
			a[p].mint= INF;			
		}
	}
	void build(int p,int l,int r){
		a[p].maxt=-INF;
		a[p].mint= INF;
		if(l==r){
			a[p].sum=a[p].maxf=a[p].minf=ra[l];
			a[p].maxs=-INF;
			a[p].mins= INF;
			a[p].maxc=1;
			a[p].minc=1;
			return;
		}
		int mi=(l+r)>>1;
		build(p<<1,l,mi);
		build(p<<1|1,mi+1,r);
		pushu(p);
	}
	
	void addu(int p,int l,int r,int nowl,int nowr,int val){
		if(r<nowl||nowr<l)return;
		if(l<=nowl&&nowr<=r){
			paddt(p,nowl,nowr,val);
			return;
		}
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);
		addu(p<<1  ,l,r,nowl,mi,val);
		addu(p<<1|1,l,r,mi+1,nowr,val);
		pushu(p);
	}
	void minu(int p,int l,int r,int nowl,int nowr,int val){
		if(r<nowl||nowr<l||a[p].maxf<=val)return;
		if(l<=nowl&&nowr<=r&&a[p].maxs<val){
			pmint(p,val);
			return;
		}
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);
		minu(p<<1  ,l,r,nowl,mi,val);
		minu(p<<1|1,l,r,mi+1,nowr,val);
		pushu(p);		
	}
	void maxu(int p,int l,int r,int nowl,int nowr,int val){
		if(r<nowl||nowr<l||a[p].minf>=val)return;
		if(l<=nowl&&nowr<=r&&a[p].mins>val){
			pmaxt(p,val);
			return;
		}
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);
		maxu(p<<1  ,l,r,nowl,mi,val);
		maxu(p<<1|1,l,r,mi+1,nowr,val);
		pushu(p);				
	}
	
	ll sumq(int p,int l,int r,int nowl,int nowr){
		if(r<nowl||nowr<l)return 0;
		if(l<=nowl&&nowr<=r)return a[p].sum;
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);		
		return sumq(p<<1,l,r,nowl,mi)+sumq(p<<1|1,l,r,mi+1,nowr);
	}
	ll minq(int p,int l,int r,int nowl,int nowr){
		if(r<nowl||nowr<l)return INF;
		if(l<=nowl&&nowr<=r)return a[p].minf;
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);		
		return min(minq(p<<1,l,r,nowl,mi),minq(p<<1|1,l,r,mi+1,nowr));		
	}
	ll maxq(int p,int l,int r,int nowl,int nowr){
		if(r<nowl||nowr<l)return -INF;
		if(l<=nowl&&nowr<=r)return a[p].maxf;
		int mi=(nowl+nowr)>>1;
		pushd(p,nowl,nowr);		
		return max(maxq(p<<1,l,r,nowl,mi),maxq(p<<1|1,l,r,mi+1,nowr));				
	}
}
using namespace seg_tree;
int n,m,op,l,r,x;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>ra[i];
	build(1,1,n);
	cin>>m;
	while(m--){
		cin>>op>>l>>r;
		if(op<4)cin>>x;
		if(op==1)addu(1,l,r,1,n,x);
		else if(op==2)maxu(1,l,r,1,n,x);
		else if(op==3)minu(1,l,r,1,n,x);
		else if(op==4)cout<<sumq(1,l,r,1,n)<<"\n";
		else if(op==5)cout<<maxq(1,l,r,1,n)<<"\n";
		else cout<<minq(1,l,r,1,n)<<"\n";
	}
	return 0;
}