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