hdoj1754 线段树--单点更新

118 阅读 0 评论 78 点赞

我是靠谱客的博主沉静小虾米，最近开发中收集的这篇文章主要介绍hdoj1754 线段树--单点更新，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目中文的，不解释了

维护一个最大值的线段树

 1 #include <stdio.h>
 2
 3 #define lson l, m, rt<<1
 4 #define rson m+1, r, rt<<1|1
 5
 6 const int maxn = 200000;
 7
 8 char cmd[2];
 9 int
n, mNum, a, b, max[maxn<<2];
10
11 int Max(int x, int y)
12 {
13
return (x>y ? x:y);
14 }/* Max */
15
16 void BuildTree(int l, int r, int rt)
17 {
18
if (l == r)
19 
{
20
scanf("%d", &max[rt]);
21
return ;
22
}/* End of If */
23
24
int m = (l+r)>>1;
25 
BuildTree(lson);
26 
BuildTree(rson);
27
max[rt] = Max(max[rt<<1], max[rt<<1|1]);
/* Push Up */
28 }/* BuildTree */
29
30 int Query(int L, int R, int l, int r, int rt)
31 {
32
if (L<=l && r<=R)
33
return max[rt];
34
35
int ret=-1, m=(l+r)>>1;
36
37
if (L <= m)
38
ret = Max(ret, Query(L, R, lson));
39
if (R > m)
40
ret = Max(ret, Query(L, R, rson));
41
42
return ret;
43 }/* Query */
44
45 void UpData(int p, int bi, int l, int r, int rt)
46 {
47
if (l == r)
48 
{
49
max[rt] = bi;
50
return ;
51
}/* End of If */
52
53
int m = (l+r)>>1;
54
55
if (p <= m)
56 
UpData(p, bi, lson);
57
else
58 
UpData(p, bi, rson);
59
60
max[rt] = Max(max[rt<<1], max[rt<<1|1]);
/* Push Up */
61 }/* UpData */
62
63 int main()
64 {
65
while (~scanf("%d %d", &n, &mNum))
66 
{
67
BuildTree(1, n, 1);
68
for (int i=1; i<=mNum; ++i)
69 
{
70
scanf("%s %d %d", cmd, &a, &b);
71
if (cmd[0] == 'Q')
/* Query */
72
printf("%dn", Query(a, b, 1, n, 1));
73
else
/* UpData */
74
UpData(a, b, 1, n, 1);
75 
}
76
}/* End of While */
77
78
return 0;
79 }