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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
template < typename T, auto op, T e, typename F, auto mapping, auto composition,
F 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;}
template<typename T,typename D>
T LAZY(T x,T lazy,D l,D r){return x + (r - l + 1) * lazy;}
using segtree_add=segtree< ll, PLUS<ll>, 0, ll,LAZY<ll,int>, PLUS<ll>, 0 >;
ll n,m,a[(int)1e5+9];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
segtree_add seg(a,n);
for(int i=1,op,x,y,z;i<=m;++i){
cin>>op>>x>>y;
if(op&1){
cin>>z;
seg.modify(x,y,z);
}else cout<<seg.query(x,y)<<"\n";
}
}
|