题目大意

题目描述清楚，不做赘述

解题思路

区修区查，考虑线段树

$op=2$ $:$ 懒标记即可

$op=3$ $:$ 正常查询即可

$op=0$ $:$ 要求将区间内所有大于 $b$ 的数修改为 $b$ 。考虑记录区间最大值 $mx1$ 与次大值 $mx2$ ，在 $b$ 仅小于最大值时，即 $mx2<b<mx1$ ，对区间进行修改。其中，$mx2$ 严格小于 $mx1$ 。

$op=1$ $:$ 操作类似于 $op=0$ 的情况

注意事项

$①$ $mx1$ $mx2$ 初始化时要设为 $±inf$

$②$ 在修改 $mx1$ 时，要判断与 $mn1$ 或 $mn2$ 是否相等，若相等则要一同修改； $mn1$ 同理

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define MID ((l+r)>>1)
#define N 200010
#define inf 1000000000000000ll
struct node{
	int l,r,sum;
	int mx1,mx2,mxnum;
	int mn1,mn2,mnnum;
	int add;
}tr[N<<2];
int n,q;
int a[N];

void apply_chgmx(int p,int val){
	if(tr[p].mx1<=val)return;
	tr[p].sum+=(val-tr[p].mx1)*tr[p].mxnum;
	if(tr[p].mn1==tr[p].mx1)tr[p].mn1=val;
	if(tr[p].mn2==tr[p].mx1)tr[p].mn2=val;
	tr[p].mx1=val;
}
void apply_chgmn(int p,int val){
	if(tr[p].mn1>=val)return;
	tr[p].sum+=(val-tr[p].mn1)*tr[p].mnnum;
	if(tr[p].mx1==tr[p].mn1)tr[p].mx1=val;
	if(tr[p].mx2==tr[p].mn1)tr[p].mx2=val;
	tr[p].mn1=val;
}
void apply_add(int p,int val){
	tr[p].sum+=val*(tr[p].r-tr[p].l+1);
	tr[p].mx1+=val;
	if(tr[p].mx2!=-inf)tr[p].mx2+=val;
	tr[p].mn1+=val;
	if(tr[p].mn2!=inf)tr[p].mn2+=val;
	tr[p].add+=val;
}

void pushup(int p){
	tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum;
	
	if(tr[lc(p)].mx1==tr[rc(p)].mx1){
		tr[p].mx1=tr[lc(p)].mx1;
		tr[p].mxnum=tr[lc(p)].mxnum+tr[rc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx2,tr[rc(p)].mx2);
	}
	else if(tr[lc(p)].mx1>tr[rc(p)].mx1){
		tr[p].mx1=tr[lc(p)].mx1;
		tr[p].mxnum=tr[lc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx2,tr[rc(p)].mx1);
	}
	else{
		tr[p].mx1=tr[rc(p)].mx1;
		tr[p].mxnum=tr[rc(p)].mxnum;
		tr[p].mx2=max(tr[lc(p)].mx1,tr[rc(p)].mx2);
	}
	
	if(tr[lc(p)].mn1==tr[rc(p)].mn1){
		tr[p].mn1=tr[lc(p)].mn1;
		tr[p].mnnum=tr[lc(p)].mnnum+tr[rc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn2,tr[rc(p)].mn2);
	}
	else if(tr[lc(p)].mn1<tr[rc(p)].mn1){
		tr[p].mn1=tr[lc(p)].mn1;
		tr[p].mnnum=tr[lc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn2,tr[rc(p)].mn1);
	}
	else{
		tr[p].mn1=tr[rc(p)].mn1;
		tr[p].mnnum=tr[rc(p)].mnnum;
		tr[p].mn2=min(tr[lc(p)].mn1,tr[rc(p)].mn2);
	}
}
void pushdown(int p){
	if(tr[p].add){
		apply_add(lc(p),tr[p].add);
		apply_add(rc(p),tr[p].add);
		tr[p].add=0;
	}
	
	if(tr[lc(p)].mx1>tr[p].mx1)apply_chgmx(lc(p),tr[p].mx1);
	if(tr[lc(p)].mn1<tr[p].mn1)apply_chgmn(lc(p),tr[p].mn1);
	
	if(tr[rc(p)].mx1>tr[p].mx1)apply_chgmx(rc(p),tr[p].mx1);
	if(tr[rc(p)].mn1<tr[p].mn1)apply_chgmn(rc(p),tr[p].mn1);
}
void build(int p,int l,int r){
	if(l==r){
		tr[p]={l,r,a[l],a[l],-inf,1,a[l],inf,1,0};
		return;
	}
	tr[p]={l,r,0,0,0,0,0,0,0,0};
	build(lc(p),l,MID);build(rc(p),MID+1,r);
	pushup(p);
}
void chgmx(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(b>=tr[p].mx1)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		if(b>tr[p].mx2){
			apply_chgmx(p,b);
			return;
		}
	}
	pushdown(p);
	chgmx(lc(p),l,r,b);chgmx(rc(p),l,r,b);
	pushup(p);
}
void chgmn(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(b<=tr[p].mn1)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		if(b<tr[p].mn2){
			apply_chgmn(p,b);
			return;
		}
	}
	pushdown(p);
	chgmn(lc(p),l,r,b);chgmn(rc(p),l,r,b);
	pushup(p);
}
void chgadd(int p,int l,int r,int b){
	if(tr[p].r<l||tr[p].l>r)return;
	if(l<=tr[p].l&&tr[p].r<=r){
		apply_add(p,b);
		return;
	}
	pushdown(p);
	chgadd(lc(p),l,r,b);chgadd(rc(p),l,r,b);
	pushup(p);
}
int query(int p,int l,int r){
	if(tr[p].r<l||tr[p].l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
	pushdown(p);
	return query(lc(p),l,r)+query(rc(p),l,r);
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(q--){
		int op,l,r,b;cin>>op>>l>>r;l++;
		if(op==0){
			cin>>b;
			chgmx(1,l,r,b);
		}
		else if(op==1){
			cin>>b;
			chgmn(1,l,r,b);
		}
		else if(op==2){
			cin>>b;
			chgadd(1,l,r,b);
		}
		else{
			cout<<query(1,l,r)<<'\n';
		}
	}
	
	return 0;
}