G

Прибавление на отрезке

public
Guest Jun 11, 2024 Never 20
Clone
C++ D.cpp 97 lines (82 loc) | 2.02 KB
1
#include <bits/stdc++.h>
2
#define ll long long
3
#define f first
4
#define s second
5
6
using namespace std;
7
8
const int inf = 1e9 + 3;
9
10
vector<ll> tree;
11
vector<ll> add;
12
vector<int> a;
13
14
void build(int v, int tl, int tr) {
15
if (tl == tr) {
16
tree[v] = a[tl];
17
add[v] = 0;
18
} else {
19
int tm = (tl + tr) / 2;
20
build(v * 2, tl, tm);
21
build(v * 2 + 1, tm + 1, tr);
22
tree[v] = tree[v * 2] + tree[v * 2 + 1];
23
add[v] = 0;
24
}
25
}
26
27
void push(int v, int tl, int tr) {
28
if (add[v] != 0) {
29
int tm = (tl + tr) / 2;
30
tree[v * 2] += (tm - tl + 1) * add[v];
31
add[v * 2] += add[v];
32
33
tree[v * 2 + 1] += (tr - tm) * add[v];
34
add[v * 2 + 1] += add[v];
35
36
add[v] = 0;
37
}
38
}
39
40
void update(int v, int tl, int tr, int l, int r, ll x) {
41
if (r < tl || tr < l) {
42
return;
43
}
44
if (l <= tl && tr <= r) {
45
tree[v] += (tr - tl + 1) * x;
46
add[v] += x;
47
return;
48
}
49
int tm = (tl + tr) / 2;
50
push(v, tl, tr);
51
update(v * 2, tl, tm, l, r, x);
52
update(v * 2 + 1, tm + 1, tr, l, r, x);
53
tree[v] = tree[v * 2] + tree[v * 2 + 1];
54
}
55
56
ll sum(int v, int tl, int tr, int l, int r) {
57
if (r < tl || tr < l) {
58
return 0;
59
}
60
61
if (l <= tl && tr <= r) {
62
return tree[v];
63
}
64
65
push(v, tl, tr);
66
int tm = (tl + tr) / 2;
67
ll s1 = sum(v * 2, tl, tm, l, r);
68
ll s2 = sum(v * 2 + 1, tm + 1, tr, l, r);
69
70
return s1 + s2;
71
}
72
73
int main() {
74
int n, m;
75
cin >> n >> m;
76
a.resize(n + 1);
77
tree.resize(4 * n);
78
add.resize(4 * n);
79
for (int i = 1; i <= n; ++i) {
80
cin >> a[i];
81
}
82
build(1, 1, n);
83
84
for (int i = 0; i < m; ++i) {
85
int op, l, r;
86
cin >> op >> l >> r;
87
if (op == 1) {
88
int x;
89
cin >> x;
90
update(1, 1, n, l, r, x);
91
} else {
92
cout << sum(1, 1, n, l, r) << endl;
93
}
94
}
95
96
return 0;
97
}