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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf = 1e18;
template < typename T, auto op, auto e, typename F, auto mapping, auto composition,
auto e1 >
class segtree
{
int n;
vector< T > v;
vector< F > lazy;
void build(int now, int l, int r, T a[])
{
if(l == r)
{
v[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid, a);
build(now * 2 + 1, mid + 1, r, a);
v[now] = op(v[now * 2], v[now * 2 + 1]);
}
void pushup(int k) { v[k] = op(v[k * 2], v[k * 2 + 1]); }
void pushdown(int k, int l, int r)
{
v[k] = mapping(v[k], lazy[k], l, r);
if (l != r) {
lazy[k * 2] = composition(lazy[k * 2], lazy[k]);
lazy[k * 2 + 1] = composition(lazy[k * 2 + 1], lazy[k]);
}
lazy[k] = e1();
}
void modify(int now, int ql, int qr, int l, int r, F x)
{
pushdown(now, l, r);
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
lazy[now] = x;
pushdown(now, l, r);
return;
}
modify(now * 2, ql, qr, l, (l + r) / 2, x);
modify(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r, x);
pushup(now);
}
T query(int now, int ql, int qr, int l, int r)
{
pushdown(now, l, r);
if (l > qr || r < ql) return e();
if (l >= ql && r <= qr) return v[now];
return op(query(now * 2, ql, qr, l, (l + r) / 2),
query(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r));
}
public:
segtree(T a[], int n) : segtree(n)
{
build(1, 1, n, a);
}
segtree(int n)
{
this->n = n;
v = vector< T >(n << 2, e());
lazy = vector< F >(n << 2, e1());
}
void modify(int l, int r, F x) { modify(1, l, r, 1, n, x); }
T query(int l, int r) { return query(1, l, r, 1, n); }
};
template<typename T>
T MAX(T x, T y) {if(x > y) return x; else return y;}
template<typename T>
T MIN(T x, T y) {if(x < y) return x; else return y;}
template<typename T>
T PLUS(T x, T y) {return x + y;}
struct F {ll add, cover;};
using segtree_max_edit=segtree< ll, [](ll x, ll y) { return max(x, y); }, [](){return -inf;}, F,
[](ll x, F t, int l, int r) {
if (t.cover != inf)
return t.cover;
else
return x + t.add;
},
[](F t1, F t2) -> F {
if (t2.cover != inf) return{ 0, t2.cover };
else
{
if (t1.cover != inf) return { 0, t1.cover + t2.add };
else return { t1.add + t2.add, inf };
}
},
[]()->F {return { 0, inf };} >;
ll n,q,a[(int)1e6+9];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i)cin>>a[i];
segtree_max_edit seg(a,n);
for(int i=1,op,l,r,x;i<=q;++i){
cin>>op>>l>>r;
if(op==1){
cin>>x;
seg.modify(l,r,F{0,x});
}else if(op==2){
cin>>x;
seg.modify(l,r,F{x,inf});
}else cout<<seg.query(l,r)<<"\n";
}
}
|