首页 > 代码库 > hdu1754 单点更新
hdu1754 单点更新
第二道线段树,哈哈哈,已经从区间求和萌萌哒变成求最大值,我是不是好无聊哦~~~~
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int maxn = 200000 + 10;10 int a[maxn];11 struct node12 {13 int l, r, v;14 15 } va[maxn<<2];16 17 void build(int l, int r, int i)18 {19 va[i].l = l;20 va[i].r = r;21 int m = (l + r)/2;22 if(l == r) {23 va[i].v = a[l];24 return ;25 }26 build(l, m, i<<1);27 build(m+1, r, i<<1|1);28 va[i].v = max(va[i<<1].v, va[i<<1|1].v);29 }30 31 void Update(int id, int num, int i)32 {33 if(va[i].l == va[i].r) {34 va[i].v = num;35 return ;36 }37 else {38 if(id <= va[i<<1].r) Update(id, num, i<<1);39 else Update(id, num, i<<1|1);40 }41 va[i].v = max(va[i<<1].v, va[i<<1|1].v);42 }43 44 int Quary(int l, int r, int i)45 {46 int m = (va[i].l + va[i].r)/2;47 if(l == va[i].l && r == va[i].r) {48 return va[i].v;49 }50 if(r <= m) return Quary(l, r, i<<1);51 else if(l > m) return Quary(l, r, i<<1|1);52 else return max(Quary(l, m, i<<1), Quary(m+1, r, i<<1|1));53 }54 int main()55 {56 //freopen("test.in", "r", stdin);57 char s[5];58 int N, M, x, y;59 while(scanf("%d%d", &N, &M) != EOF) {60 for(int i = 1; i <= N; i++) {61 scanf("%d", &a[i]);62 }63 build(1, N, 1);64 while(M--) {65 scanf("%s %d %d", s, &x, &y);66 if(s[0] == ‘Q‘) printf("%d\n", Quary(x, y, 1));67 else Update(x, y, 1);68 }69 }70 return 0;71 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。