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
| struct Node {
int L, R;
ll num, lazy;
Node() {}
Node(int L, int R, ll num) : L(L), R(R), num(num) {}
Node operator + (Node &you) const {
return Node(min(L, you.L), max(R, you.R), num + you.num);
}
};
class SegTree {
private :
Node node[N << 2];
public :
void Add(int p, ll v) {
node[p].lazy += v;
node[p].num += v * (node[p].R - node[p].L + 1);
}
void Pushdown(int p) {
if(node[p].lazy == 0) return ;
Add(p << 1, node[p].lazy);
Add(p << 1 | 1, node[p].lazy);
node[p].lazy = 0;
}
void Build(int p, int L, int R, int *a) {
node[p].L = L, node[p].R = R, node[p].lazy = 0;
if(L == R) {
node[p].num = a[L];
return ;
}
int mid = L + R >> 1;
Build(p << 1, L, mid, a);
Build(p << 1 | 1, mid + 1, R, a);
node[p] = node[p << 1] + node[p << 1 | 1];
}
void ModifyRange(int p, int L, int R, ll v) {
if(L <= node[p].L && node[p].R <= R) {
Add(p, v);
return ;
}
Pushdown(p);
int mid = node[p].L + node[p].R >> 1;
if(L <= mid) ModifyRange(p << 1, L, R, v);
if(mid < R) ModifyRange(p << 1 | 1, L, R, v);
node[p] = node[p << 1] + node[p << 1 | 1];
}
long long QueryRange(int p, int L, int R) {
if(L <= node[p].L && node[p].R <= R) {
return node[p].num;
}
Pushdown(p);
int mid = node[p].L + node[p].R >> 1;
long long ans = 0;
if(L <= mid) ans += QueryRange(p << 1, L, R);
if(mid < R) ans += QueryRange(p << 1 | 1, L, R);
return ans;
}
};
|
