Segment tree beats~

Segment tree beats!

Designed to practice Mr. Ji, the tree , And save a board ~

#576 (Div. 2) D. Welfare State

The interval is taken as $max$ The naked question of , For taking $max$ operation , Maintenance minimum 、 Second minimum 、 Minimum number , It can be maintained by marking take $max$ Operation ;
The interval is taken as $min$ The operation of similarly .

#include<bits/stdc++.h>
using namespace std;

inline int qread(){
    
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}

int n,m;
int a[200050];
struct node{
    
	int mi,smi,cnt,tag;
}tr[800050];
void pushup(int p){
    
	if(tr[2*p].mi<tr[2*p+1].mi){
    
		tr[p].mi=tr[2*p].mi;tr[p].cnt=tr[2*p].cnt;
		tr[p].smi=min(tr[2*p+1].mi,tr[2*p].smi);
	}else if(tr[2*p].mi>tr[2*p+1].mi){
    
		tr[p].mi=tr[2*p+1].mi;tr[p].cnt=tr[2*p+1].cnt;
		tr[p].smi=min(tr[2*p].mi,tr[2*p+1].smi);
	}else {
    
		tr[p].mi=tr[2*p].mi;tr[p].cnt=tr[2*p].cnt+tr[2*p+1].cnt;
		tr[p].smi=min(tr[2*p].smi,tr[2*p+1].smi);
	}
}
void build(int p,int l,int r){
    
	tr[p].tag=-1;
	if(l==r){
    
		tr[p].mi=a[l];
		tr[p].smi=1e9+7;
		tr[p].cnt=1;
		return;
	}
	int mid=l+r>>1;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	pushup(p);
}
void pushdown(int p){
    
	if(tr[p].tag==-1)return ;
	if(tr[p].tag>tr[2*p].mi){
    
		tr[2*p].mi=tr[2*p].tag=tr[p].tag;
	}
	if(tr[p].tag>tr[2*p+1].mi){
    
		tr[2*p+1].mi=tr[2*p+1].tag=tr[p].tag;
	}
	tr[p].tag=-1;
} 
void update(int p,int l,int r,int w){
    
	if(tr[p].mi>=w)return;
	if(tr[p].smi>w){
    
		tr[p].mi=tr[p].tag=w;
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	update(2*p,l,mid,w);update(2*p+1,mid+1,r,w);
	pushup(p);
}
void update1(int p,int l,int r,int x,int w){
    
	if(l==r){
    
		tr[p].mi=w;
		return;
	}
	int mid=l+r>>1;pushdown(p);
	if(x<=mid)update1(2*p,l,mid,x,w);
	else update1(2*p+1,mid+1,r,x,w);
	pushup(p);
}
int query(int p,int l,int r,int x){
    
	if(l==r)return tr[p].mi;
	int mid=l+r>>1;
	pushdown(p);
	if(x<=mid)return query(2*p,l,mid,x);
	else return query(2*p+1,mid+1,r,x); 
}
int main()
{
    
	n=qread();
	for(int i=1;i<=n;i++){
    
		a[i]=qread();
	}
	build(1,1,n);
	m=qread();
	for(int i=1;i<=m;i++){
    
		int op;
		op=qread();
		if(op==1){
    
			int a,b;
			a=qread();b=qread();
			update1(1,1,n,a,b);
		}else {
    
			int a;a=qread();
			update(1,1,n,a);
		}
	}
	for(int i=1;i<=n;i++){
    
		printf("%d ",query(1,1,n,i));
	}
	return 0;
}

UOJ #4695. The most fake female player

The length of the array $n$ , Operands $m$ All for $5e5$;
Five operations ：
1. Give me an interval $[L,R]$ Add a number $x$
2. Put an interval $[L,R]$ Less than $x$ The number becomes $x$
3. Put an interval $[L,R]$ Li greater than $x$ The number becomes $x$
4. Find interval $[L,R]$ And
5. Find interval $[L,R]$ The maximum of
6. Find interval $[L,R]$ The minimum value of

Take in the interval $min$ 、 take $max$ On the basis of , Add the operation of interval addition ：
Maintain minimum values separately 、 Maximum 、 Mark other values ;
Interval plus operation Is to add all three marks ; The interval is taken as $min$ The operation is to modify the mark on the maximum value ; take $max$ Empathy .

Two points of attention ：
Take the addition and subtraction marks on the maximum value as an example . When downloading this mark, it is necessary to judge whether the sub interval contains the maximum value , If it is not included, the plus and minus marks of other values should be transmitted down ;
If the value range of an interval is very small （ Only $1$ or $2$ Number ）, It may happen that a value is both a maximum value and a sub minimum value , That is, the number field overlaps . This situation requires special judgment , Distinguish which marker should be used .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int qread(){
    
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}

const int INF=2e9;
int n,m;
int s[500050];
struct node{
    
	// Maximum 、 Second largest value 、 Maximum number 、 minimum value 、 Second minimum 、 Minimum number  
	int mx,smx,cmx,mi,smi,cmi;
	ll sum;
	// minimum value 、 Maximum 、 Modification mark of other values  
	int add1,add2,add3;
}tr[2000050];
#define ls (p<<1)
#define rs (p<<1|1)
void pushup(int p){
    
	tr[p].sum=tr[ls].sum+tr[rs].sum;
	if(tr[ls].mi==tr[rs].mi){
    
		tr[p].mi=tr[ls].mi;
		tr[p].smi=min(tr[ls].smi,tr[rs].smi);
		tr[p].cmi=tr[ls].cmi+tr[rs].cmi;
	}else if(tr[ls].mi<tr[rs].mi){
    
		tr[p].mi=tr[ls].mi;
		tr[p].smi=min(tr[ls].smi,tr[rs].mi);
		tr[p].cmi=tr[ls].cmi; 
	}else {
    
		tr[p].mi=tr[rs].mi;
		tr[p].smi=min(tr[ls].mi,tr[rs].smi);
		tr[p].cmi=tr[rs].cmi;
	}
	if(tr[ls].mx==tr[rs].mx){
    
		tr[p].mx=tr[ls].mx;
		tr[p].smx=max(tr[ls].smx,tr[rs].smx);
		tr[p].cmx=tr[ls].cmx+tr[rs].cmx; 
	}else if(tr[ls].mx>tr[rs].mx){
    
		tr[p].mx=tr[ls].mx;
		tr[p].smx=max(tr[ls].smx,tr[rs].mx);
		tr[p].cmx=tr[ls].cmx;
	}else {
    
		tr[p].mx=tr[rs].mx;
		tr[p].smx=max(tr[ls].mx,tr[rs].smx);
		tr[p].cmx=tr[rs].cmx;
	}
}
// Yes tr[p] Modification of ,k1、k2、k3  They are the minimum values 、 Maximum 、 Tags for other values  
void update(int p,int l,int r,int k1,int k2,int k3){
    
	if(tr[p].mi==tr[p].mx){
    
		// If the interval has only one value , Only the maximum value should be applied 、 The addition and subtraction marks of the minimum value  
		if(k1==k3)k1=k2;
		else k2=k1;
		tr[p].sum+=1LL*k1*tr[p].cmi;
	}else{
    
		tr[p].sum+=1LL*k1*tr[p].cmi+1LL*k2*tr[p].cmx+1LL*k3*(r-l+1-tr[p].cmi-tr[p].cmx);
	}
	// The second smallest value is the maximum value , It should be marked by the maximum value  
	if(tr[p].smi==tr[p].mx)tr[p].smi+=k2;
	else if(tr[p].smi!=INF)tr[p].smi+=k3;// Otherwise, it will be marked by other values 
	
	if(tr[p].smx==tr[p].mi)tr[p].smx+=k1;
	else if(tr[p].smx!=INF)tr[p].smx+=k3; 
	
	tr[p].mi+=k1;tr[p].mx+=k2;
	tr[p].add1+=k1;tr[p].add2+=k2;tr[p].add3+=k3;
}
void pushdown(int p,int l,int r){
    
	int mi=min(tr[ls].mi,tr[rs].mi);
	int mx=max(tr[ls].mx,tr[rs].mx);
	int mid=l+r>>1;
	update(ls,l,mid,tr[ls].mi==mi?tr[p].add1:tr[p].add3,
		tr[ls].mx==mx?tr[p].add2:tr[p].add3,tr[p].add3);
	update(rs,mid+1,r,tr[rs].mi==mi?tr[p].add1:tr[p].add3,
		tr[rs].mx==mx?tr[p].add2:tr[p].add3,tr[p].add3);
	
	tr[p].add1=tr[p].add2=tr[p].add3=0;
}
void build(int p,int l,int r){
    
	tr[p].add1=tr[p].add2=tr[p].add3=0;
	if(l==r){
    
		tr[p].sum=tr[p].mi=tr[p].mx=s[l];
		tr[p].smi=INF;tr[p].smx=-INF;
		tr[p].cmi=tr[p].cmx=1;
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p); 
}
void update1(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		update(p,l,r,w,w,w);
		return;
	}
	int mid=l+r>>1;
	pushdown(p,l,r);
	if(x<=mid)update1(2*p,l,mid,x,y,w);
	if(mid<y)update1(2*p+1,mid+1,r,x,y,w);
	pushup(p);
}
void update2(int p,int l,int r,int x,int y,int w){
    
	if(tr[p].mi>=w)return;
	if(x<=l&&r<=y&&tr[p].smi>w){
    
		update(p,l,r,w-tr[p].mi,0,0);
		return;
	}
	pushdown(p,l,r);
	int mid=l+r>>1;
	if(x<=mid)update2(ls,l,mid,x,y,w);
	if(mid<y)update2(rs,mid+1,r,x,y,w);
	pushup(p);
}
void update3(int p,int l,int r,int x,int y,int w){
    
	if(tr[p].mx<=w)return;
	if(x<=l&&r<=y&&tr[p].smx<w){
    
		update(p,l,r,0,w-tr[p].mx,0);
		return;
	}
	int mid=l+r>>1;
	pushdown(p,l,r);
	if(x<=mid)update3(ls,l,mid,x,y,w);
	if(mid<y)update3(rs,mid+1,r,x,y,w);
	pushup(p);
}
ll query1(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].sum;
	int mid=l+r>>1;
	pushdown(p,l,r);
	ll ans=0;
	if(x<=mid)ans+=query1(ls,l,mid,x,y);
	if(mid<y)ans+=query1(rs,mid+1,r,x,y);
	return ans;
}
int query2(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mx;
	int mid=l+r>>1,ans=-INF;
	pushdown(p,l,r);
	if(x<=mid)ans=max(ans,query2(ls,l,mid,x,y));
	if(mid<y)ans=max(ans,query2(rs,mid+1,r,x,y));
	return ans;
}
int query3(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mi;
	int mid=l+r>>1,ans=INF;
	pushdown(p,l,r);
	if(x<=mid)ans=min(ans,query3(ls,l,mid,x,y));
	if(mid<y)ans=min(ans,query3(rs,mid+1,r,x,y));
	return ans; 
}
#undef ls
#undef rs
int main(){
    
	n=qread();
	for(int i=1;i<=n;i++)s[i]=qread();
	build(1,1,n);
	m=qread();
	while(m--){
    
		int op=qread(),l=qread(),r=qread();
		int x;
		if(op<=3)x=qread();
		if(op==1)update1(1,1,n,l,r,x);
		else if(op==2)update2(1,1,n,l,r,x);
		else if(op==3)update3(1,1,n,l,r,x);
		else if(op==4)printf("%lld\n",query1(1,1,n,l,r));
		else if(op==5)printf("%d\n",query2(1,1,n,l,r));
		else printf("%d\n",query3(1,1,n,l,r));
	}
	return 0;
}

#3064. Tyvj 1518 CPU monitor

Maintain five tags , Interval is marked 、 Interval assignment mark 、 Mark the largest interval in history 、 Interval history maximum assignment mark 、 Whether there is assignment mark .
This tag can be merged , After the interval assignment, add , Directly add it to the assignment .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int qread(){
    
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}
    
const int INF=2e9;
int n,m;
int s[100050];
struct node{
    
	// Interval maximum 、 Interval historical maximum  
	int mx,mx_;
	// Interval is marked 、 Interval coverage mark 、 Mark the largest interval in history 、 Interval history maximum coverage mark  
	int add,cov,add_,cov_;
	int tag;// Whether it is covered by the interval  
}tr[400050];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
void pushup(int p){
    
	tr[p].mx=max(tr[ls].mx,tr[rs].mx);
	tr[p].mx_=max(tr[ls].mx_,tr[rs].mx_);
}
void plu(int p,int k1,int k2){
    
	tr[p].mx_=max(tr[p].mx_,tr[p].mx+k2);
	tr[p].mx+=k1;
	if(tr[p].tag){
    
		tr[p].cov_=max(tr[p].cov_,tr[p].cov+k2);
		tr[p].cov+=k1;
	}else{
    
		tr[p].add_=max(tr[p].add_,tr[p].add+k2);
		tr[p].add+=k1;
	}
}
void cov(int p,int k1,int k2){
    
	tr[p].mx_=max(tr[p].mx_,k2);
	tr[p].mx=k1;
	tr[p].cov_=max(tr[p].cov_,k2);
	tr[p].cov=k1;
	tr[p].tag=1;
}
void pushdown(int p){
    
	if(tr[p].add){
    
		plu(ls,tr[p].add,tr[p].add_);
		plu(rs,tr[p].add,tr[p].add_);
		tr[p].add=0;tr[p].add_=0;
	}
	if(tr[p].tag){
    
		cov(ls,tr[p].cov,tr[p].cov_);
		cov(rs,tr[p].cov,tr[p].cov_);
		tr[p].tag=0;tr[p].cov_=INT_MIN;
	}
}
void build(int p,int l,int r){
    
	tr[p].tag=0;tr[p].add=0;tr[p].add_=0;
	tr[p].cov_=INT_MIN;
	if(l==r){
    
		tr[p].mx=tr[p].mx_=s[l];
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}
void update1(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		plu(p,w,w);
		return;
	}
	pushdown(p);
	if(x<=mid)update1(ls,l,mid,x,y,w);
	if(mid<y)update1(rs,mid+1,r,x,y,w);
	pushup(p);
}
void update2(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		cov(p,w,w);
		return;
	}
	pushdown(p);
	if(x<=mid)update2(ls,l,mid,x,y,w);
	if(mid<y)update2(rs,mid+1,r,x,y,w);
	pushup(p);
}
int query1(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mx;
	pushdown(p);
	int ans=INT_MIN;
	if(x<=mid)ans=max(ans,query1(ls,l,mid,x,y));
	if(mid<y)ans=max(ans,query1(rs,mid+1,r,x,y));
	return ans;
} 
int query2(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mx_;
	pushdown(p);
	int ans=INT_MIN;
	if(x<=mid)ans=max(ans,query2(ls,l,mid,x,y));
	if(mid<y)ans=max(ans,query2(rs,mid+1,r,x,y));
	return ans;
} 
#undef ls
#undef rs
#undef mid 
int main(){
    
	n=qread();
	for(int i=1;i<=n;i++)s[i]=qread();
	m=qread();
	build(1,1,n);
	for(int i=1;i<=m;i++){
    
		char ss[4];scanf("%s",ss);
		int a=qread(),b=qread();
		if(ss[0]=='Q'){
    
			printf("%d\n",query1(1,1,n,a,b));
		}else if(ss[0]=='A'){
    
			printf("%d\n",query2(1,1,n,a,b));
		}else if(ss[0]=='P'){
    
			int c=qread();
			update1(1,1,n,a,b,c);
		}else {
    
			int c=qread();
			update2(1,1,n,a,b,c);
		}
	}
	return 0;
}

#164. 【 Tsinghua training 2015】V

give l,r,k, For all i∈[l,r], take A[i] add k;
give l,r,k, For all i∈[l,r], take A[i] become max(A[i]-k,0);
give l,r,k, For all i∈[l,r], take A[i]=k;
give p, inquiry A[p]
give p, inquiry B[p]

Maintain two tags , Add before take $max$, It can be combined .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
inline int qread(){
    
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}
    
const ll INF=1e18;
int n,m;
int s[500050];
struct node{
    
	pll his,now;
}tr[2000050];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
pll merge(pll a,pll b){
    
	return make_pair(max(a.first+b.first,-INF),max(a.second+b.first,b.second));
}
pll getmx(pll a,pll b){
    
	return make_pair(max(a.first,b.first),max(a.second,b.second));
}
void update(int p,pll k1,pll k2){
    
	tr[p].his=getmx(tr[p].his,merge(tr[p].now,k2));
	tr[p].now=merge(tr[p].now,k1);
}
void pushdown(int p){
    
	update(ls,tr[p].now,tr[p].his);
	update(rs,tr[p].now,tr[p].his);
	tr[p].now=tr[p].his=make_pair(0,0);
}
void build(int p,int l,int r){
    
	tr[p].now=tr[p].his=make_pair(0,0);
	if(l==r){
    
		tr[p].now=tr[p].his=make_pair(s[l],0);
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void update1(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		update(p,make_pair(w,0),make_pair(w,0));
		return;
	}
	pushdown(p);
	if(x<=mid)update1(ls,l,mid,x,y,w);
	if(mid<y)update1(rs,mid+1,r,x,y,w);
}
void update2(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		update(p,make_pair(-w,0),make_pair(-w,0));
		return;
	}
	pushdown(p);
	if(x<=mid)update2(ls,l,mid,x,y,w);
	if(mid<y)update2(rs,mid+1,r,x,y,w);
}
void update3(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		update(p,make_pair(-INF,w),make_pair(-INF,w));
		return;
	}
	pushdown(p);
	if(x<=mid)update3(ls,l,mid,x,y,w);
	if(mid<y)update3(rs,mid+1,r,x,y,w);
}
ll query1(int p,int l,int r,int x){
    
	if(l==r)return max(tr[p].now.first,tr[p].now.second);
	pushdown(p);
	if(x<=mid)return query1(ls,l,mid,x);
	else return query1(rs,mid+1,r,x); 
}
ll query2(int p,int l,int r,int x){
    
	if(l==r)return max(tr[p].his.first,tr[p].his.second);
	pushdown(p);
	if(x<=mid)return query2(ls,l,mid,x);
	else return query2(rs,mid+1,r,x); 
}

#undef ls
#undef rs
#undef mid 
int main(){
    
	n=qread(),m=qread();
	for(int i=1;i<=n;i++)s[i]=qread();
	build(1,1,n);
	for(int i=1;i<=m;i++){
    
		int op=qread(),l=qread(),r;
		int x;
		if(op<=3)r=qread(),x=qread();
		if(op==1){
    
			update1(1,1,n,l,r,x);
		}else if(op==2){
    
			update2(1,1,n,l,r,x);
		}else if(op==3){
    
			update3(1,1,n,l,r,x);
		}else if(op==4){
    
			printf("%lld\n",query1(1,1,n,l));
		}else printf("%lld\n",query2(1,1,n,l));
	}
	return 0;
}

#169. 【UR #11】 New year's day old man and series

 Give a length of  n=5e5  Sequence A, Define auxiliary array  B, Initially with  A Exactly the same . give  m=5e5  operations , Each operation is one of the following four types ：
1、 give  l,r,k, For all  i∈[l,r], take  A[i] add  k;
2、 give  l,r,k, For all  i∈[l,r], take  A[i]=max(A[i],k);
3、 give  l,r, Find sequence  A  Section  [l,r]  The minimum value of ;
4、 give  l,r, Find sequence  B  Section  [l,r]  The minimum value of .
 After each operation , For all  i, take  B[i]=min(B[i],A[i]);

Divide by number field , Mark the minimum maintenance value 、 Others are worth marking 、 The historical minimum of the minimum is marked 、 The historical minimum of other values is marked Can be in $O(mlo{g}^{2}n)$ complete

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
inline int qread(){
    
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}
    
const int INF=2e9;
int n,m;
int s[500050];
struct node{
    
	int mi,smi,add1,add2,mi_;
	int add1_,add2_;
}tr[2000050];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
void pushup(int p){
    
	tr[p].mi_=min(tr[ls].mi_,tr[rs].mi_);
	if(tr[ls].mi==tr[rs].mi){
    
		tr[p].mi=tr[ls].mi;
		tr[p].smi=min(tr[ls].smi,tr[rs].smi);
	}else if(tr[ls].mi<tr[rs].mi){
    
		tr[p].mi=tr[ls].mi;
		tr[p].smi=min(tr[ls].smi,tr[rs].mi);
	}else {
    
		tr[p].mi=tr[rs].mi;
		tr[p].smi=min(tr[ls].mi,tr[rs].smi);
	}
}
void update(int p,int k1,int k1_,int k2,int k2_){
    
	tr[p].mi_=min(tr[p].mi_,tr[p].mi+k1_);
	tr[p].mi=tr[p].mi+k1;
	tr[p].add1_=min(tr[p].add1_,tr[p].add1+k1_);
	tr[p].add1+=k1;
	if(tr[p].smi!=INF)
		tr[p].smi+=k2,tr[p].add2_=min(tr[p].add2_,tr[p].add2+k2_),tr[p].add2+=k2;
}
void pushdown(int p){
    
	int mi=min(tr[ls].mi,tr[rs].mi);
	if(tr[ls].mi==mi)update(ls,tr[p].add1,tr[p].add1_,tr[p].add2,tr[p].add2_);
	else update(ls,tr[p].add2,tr[p].add2_,tr[p].add2,tr[p].add2_);
	if(tr[rs].mi==mi)update(rs,tr[p].add1,tr[p].add1_,tr[p].add2,tr[p].add2_);
	else update(rs,tr[p].add2,tr[p].add2_,tr[p].add2,tr[p].add2_); 
	tr[p].add1=tr[p].add1_=tr[p].add2=tr[p].add2_=0;
}
void build(int p,int l,int r){
    
	tr[p].add1=tr[p].add1_=tr[p].add2=tr[p].add2_=0;
	if(l==r){
    
		tr[p].mi=tr[p].mi_=s[l];
		tr[p].smi=INF;
		return ;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}
void update1(int p,int l,int r,int x,int y,int w){
    
	if(x<=l&&r<=y){
    
		update(p,w,w,w,w);
		return;
	}
	pushdown(p);
	if(x<=mid)update1(ls,l,mid,x,y,w);
	if(mid<y)update1(rs,mid+1,r,x,y,w);
	pushup(p);
}
void update2(int p,int l,int r,int x,int y,int w){
    
	if(tr[p].mi>=w)return;
	if(x<=l&&r<=y&&tr[p].smi>w){
    
		update(p,w-tr[p].mi,w-tr[p].mi,0,0);
		return;
	} 
	pushdown(p);
	if(x<=mid)update2(ls,l,mid,x,y,w);
	if(mid<y)update2(rs,mid+1,r,x,y,w);
	pushup(p);
}
int query1(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mi;
	int ans=INF;
	pushdown(p);
	if(x<=mid)ans=min(ans,query1(ls,l,mid,x,y));
	if(mid<y)ans=min(ans,query1(rs,mid+1,r,x,y));
	return ans;
}
int query2(int p,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tr[p].mi_;
	int ans=INF;
	pushdown(p);
	if(x<=mid)ans=min(ans,query2(ls,l,mid,x,y));
	if(mid<y)ans=min(ans,query2(rs,mid+1,r,x,y));
	return ans;
}
#undef ls
#undef rs
#undef mid 
int main(){
    
	n=qread(),m=qread();
	for(int i=1;i<=n;i++)s[i]=qread();
	build(1,1,n);
	for(int i=1;i<=m;i++){
    
		int op=qread(),l=qread(),r=qread();
		int x;
		if(op<=2)x=qread();
		if(op==1)update1(1,1,n,l,r,x);
		else if(op==2)update2(1,1,n,l,r,x);
		else if(op==3)printf("%d\n",query1(1,1,n,l,r));
		else if(op==4)printf("%d\n",query2(1,1,n,l,r));
	}
	
	return 0;
}