题意分析
区间操作，想到线段树是显然的，对于四个操作：
-
给 $[l,r]$ 增加 $x$。
-
给 $[l,r]$ 对 $x$ 取 $\min$，记为 $\operatorname{chkmin}$。
-
这个有一点意思。
一开始以为是区间覆盖，但是一个区域实际上可以种多棵树。然而，一个区域内的所有树，只有最高的那一棵对于答案有影响。
因此我们也仅仅需要维护最高的那一棵，这个操作也就等价于给 $[l,r]$ 对 $x$ 取 $\max$，记为 $\operatorname{chkmax}$。
-
查询 $[l,r]$ 的最大值。
区间最值操作，显然可以用吉司机线段树维护。
时间复杂度 $\mathcal O\left(m\log^2n\right)$。
吉司机线段树
类似于最假女选手，考虑本题如何维护。
吉司机线段树区间最值操作本质上就是将数集划分为最值、非最值来分别维护，从而将区间最值操作转化为对于最值的区间加减操作。（当然，你不需要维护区间和的时候，直接对最值取最值是一样的。）
先不考虑区间加减。
以维护区间 $\operatorname{chkmin}$ 为例，区间 $\operatorname{chkmax}$ 是类似的。
传统线段树似乎无法很好的维护，每次操作中我们的操作对象都是那些大于 $x$ 的数，而不是整个区间。那么我们考虑单独维护区间 $[l,r]$ 内的最大值 $\textit{max}$、最大值的个数 $\textit{cnt}$、次大值 $\textit{max}_2$。
这些信息都是很好上传维护的。
而区间 $[l,r]$ 对 $x$ 取 $\min$ 时：
-
若 $\textit{max}\leq x$，则取 $\min$ 后肯定不变，无需操作。
-
若 $\textit{max}_2<x<\textit{max}$，则取 $\min$ 后所有的 $\textit{max}$ 都变为了 $x$，且其余所有部分都不变。
之后令 $\textit{max}\leftarrow x$，并且打一个懒标记 $\textit{tagMax}\leftarrow x$ 即可。
-
否则，就暴力递归处理。
原论文中证明不带区间加减的区间最值操作复杂度为 $\mathcal O(m\log n)$，但是在 $2025$ 年末被证伪，复杂度下界均为 $\mathcal O\left(m\log^2n\right)$。
而同时维护 $\operatorname{chkmin},\operatorname{chkmax}$ 时，需要注意数集重合。即如果存在 $\textit{max}=\textit{min},\textit{max}=\textit{min}_2,\textit{max}_2=\textit{min}$ 的时候要一起更新。这是因为区间里的数很少。
现在考虑区间加减。
钦定加减运算优先级高于区间最值（因为加法关于最值操作有分配律）。
这样，区间加 $x$ 的时候，将对应的 $\textit{max},\textit{min}$ 加 $x$，对应的次最值、标记也增加 $x$ 即可。
AC 代码
其实是从最假女选手复制过来改的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
#define int ll
typedef long long ll;
constexpr const int N=5e5;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,a[N+1];
struct segTree{
struct node{
int l,r;
ll tagAdd;
int cntMax,cntMin;
ll max,max2,tagMax;
ll min,min2,tagMin;
int size(){
return r-l+1;
}
}t[N<<2|1];
void up(int p){
if(t[p<<1].max>t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cntMax=t[p<<1].cntMax;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max);
}else if(t[p<<1].max==t[p<<1|1].max){
t[p].max=t[p<<1].max;
t[p].cntMax=t[p<<1].cntMax+t[p<<1|1].cntMax;
t[p].max2=::max(t[p<<1].max2,t[p<<1|1].max2);
}else{
t[p].max=t[p<<1|1].max;
t[p].cntMax=t[p<<1|1].cntMax;
t[p].max2=::max(t[p<<1].max,t[p<<1|1].max2);
}
if(t[p<<1].min<t[p<<1|1].min){
t[p].min=t[p<<1].min;
t[p].cntMin=t[p<<1].cntMin;
t[p].min2=::min(t[p<<1].min2,t[p<<1|1].min);
}else if(t[p<<1].min==t[p<<1|1].min){
t[p].min=t[p<<1].min;
t[p].cntMin=t[p<<1].cntMin+t[p<<1|1].cntMin;
t[p].min2=::min(t[p<<1].min2,t[p<<1|1].min2);
}else{
t[p].min=t[p<<1|1].min;
t[p].cntMin=t[p<<1|1].cntMin;
t[p].min2=::min(t[p<<1].min,t[p<<1|1].min2);
}
}
void build(int p,int l,int r){
t[p]={l,r};
t[p].tagMax=-inf;
t[p].tagMin=inf;
if(l==r){
t[p].max=t[p].min=a[l];
t[p].max2=-inf,t[p].min2=inf;
t[p].cntMax=t[p].cntMin=1;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void downAdd(int p,ll x){
t[p].tagAdd+=x;
t[p].max+=x;
if(t[p].max2!=-inf){
t[p].max2+=x;
}
if(t[p].tagMax!=-inf){
t[p].tagMax+=x;
}
t[p].min+=x;
if(t[p].min2!=inf){
t[p].min2+=x;
}
if(t[p].tagMin!=inf){
t[p].tagMin+=x;
}
}
void downMax(int p,ll x){
if(t[p].min>x){
return;
}
t[p].tagMax=x;
if(t[p].max2==t[p].min){
t[p].max2=x;
}
if(t[p].max==t[p].min){
t[p].max=x;
}
t[p].min=x;
if(t[p].tagMin<x){
t[p].tagMin=x;
}
}
void downMin(int p,ll x){
if(t[p].max<=x){
return;
}
t[p].tagMin=x;
if(t[p].min2==t[p].max){
t[p].min2=x;
}
if(t[p].min==t[p].max){
t[p].min=x;
}
t[p].max=x;
if(t[p].tagMax>x){
t[p].tagMax=x;
}
}
void down(int p){
if(t[p].tagAdd){
downAdd(p<<1,t[p].tagAdd);
downAdd(p<<1|1,t[p].tagAdd);
t[p].tagAdd=0;
}
if(t[p].tagMax!=-inf){
downMax(p<<1,t[p].tagMax);
downMax(p<<1|1,t[p].tagMax);
t[p].tagMax=-inf;
}
if(t[p].tagMin!=inf){
downMin(p<<1,t[p].tagMin);
downMin(p<<1|1,t[p].tagMin);
t[p].tagMin=inf;
}
}
void add(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
downAdd(p,x);
return;
}
down(p);
if(l<=t[p<<1].r){
add(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
add(p<<1|1,l,r,x);
}
up(p);
}
void chkmax(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
if(x<=t[p].min){
return;
}else if(x<t[p].min2){
downMax(p,x);
return;
}
}
down(p);
if(l<=t[p<<1].r){
chkmax(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
chkmax(p<<1|1,l,r,x);
}
up(p);
}
void chkmin(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r){
if(t[p].max<=x){
return;
}else if(t[p].max2<x){
downMin(p,x);
return;
}
}
down(p);
if(l<=t[p<<1].r){
chkmin(p<<1,l,r,x);
}
if(t[p<<1|1].l<=r){
chkmin(p<<1|1,l,r,x);
}
up(p);
}
ll max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].max;
}
down(p);
ll ans=-inf;
if(l<=t[p<<1].r){
ans=max(p<<1,l,r);
}
if(t[p<<1|1].l<=r){
ans=::max(ans,max(p<<1|1,l,r));
}
return ans;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
t.build(1,1,n);
while(m--){
int op,l,r,x;
cin>>op>>l>>r;
ll pl;
switch(op){
case 1:
cin>>x;
t.add(1,l,r,x);
break;
case 2:
cin>>x;
t.chkmin(1,l,r,x);
break;
case 3:
cin>>x;
t.chkmax(1,l,r,x);
break;
case 4:
cout<<t.max(1,l,r)<<'\n';
break;
}
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
