线段树模板（求最大最小）

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
#include<cstdio>
const int INF = 0xffffff0;
const long long IINF = 1e18;
int minV = INF;
int maxV = -INF;
int max(int &a, int &b)
{
return a > b ? a : b;
}
int min(int &a, int &b)
{
return a < b ? a : b;
}
struct Node//不要左右子节点指针的做法
{
int L, R;
int minV, maxV;
int Mid()
{
return (L + R) / 2;
}
}tree[800000];//4倍叶子节点的数量就够
void BuildTree(int root, int L, int R)
{
tree[root].L = L;
tree[root].R = R;
tree[root].minV = INF;
tree[root].maxV = -INF;
if (L != R)
{
BuildTree(2 * root + 1, L, (L + R) / 2);
BuildTree(2 * root + 2, (L + R) / 2 + 1, R);
}
}
void Insert(int root, int i, int v)//将第i个数，其值为v，插入线段树
{
if (tree[root].L == tree[root].R)
{
tree[root].minV = tree[root].maxV = v;
return;
}
tree[root].minV = min(tree[root].minV, v);
tree[root].maxV = max(tree[root].maxV, v);
if (i <= tree[root].Mid())Insert(2 * root + 1, i, v);
else Insert(2 * root + 2, i, v);
}
void Query(int root, int s, int e)//查询区间[s,e]中的最小值和最大值，如果更优就记录在全
{
if (tree[root].minV >= minV&&tree[root].maxV <= maxV)
{
return;
}
if (tree[root].L == s&&tree[root].R == e)
{
minV = min(minV, tree[root].minV);
maxV = max(maxV, tree[root].maxV);
return;
}
if (e <= tree[root].Mid())Query(2 * root + 1, s, e);
else if (s > tree[root].Mid())Query(2 * root + 2, s, e);
else
{
Query(2 * root + 1, s, tree[root].Mid());
Query(2 * root + 2, tree[root].Mid() + 1, e);
}
}
int main()
{
int n, q, h;
int i, j, k;
while (scanf("%d%d", &n, &q))
{
BuildTree(0, 1, n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &h);
Insert(0, i, h);
}
for (int i = 0; i < q; i++)
{
int s, e;
char ch[3];
scanf("%s", ch);
if (ch[0] == 'Q')
{
scanf("%d%d", &s, &e);
minV = INF;
maxV = -INF;
Query(0, s, e);
printf("%dn", maxV);
}
else
{
scanf("%d%d", &s, &e);
Insert(0, s, e);
}
}
}
return 0;
}