HDU 1754 I Hate It——单点更新的线段树

HDU 1754 I Hate It——单点更新的线段树

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0字符 C (只取'Q'或'U') ，和两个正整数A，B。 当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 Output 对于每一次询问操作，在一行里面输出最高成绩。 Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output

5 6 5 9

套用单点更新，动态查询最大值的线段树模板

#include #include #include #define ls b, mid, cur<<1#define rs mid + 1, e, cur<<1|1using namespace std;const int maxid = 800000 + 10;int segtree[maxid];void up(int cur) { segtree[cur] = max(segtree[cur<<1], segtree[cur<<1|1]);}void build(int b, int e, int cur) { if (b == e) { scanf("%d", &segtree[cur]); return; } int mid = (b + e) >> 1; build(ls); build(rs); up(cur);}void update(int b, int e, int cur, int pos, int score) { if (b == e) { segtree[cur] = score; return; } int mid = (b + e) >> 1; if (pos <= mid) update(ls, pos, score); else update(rs, pos, score); up(cur);}int query(int b, int e, int cur, int l, int r) { if (b >= l && e <= r) return segtree[cur]; int mid = (b + e) >> 1, ans = 0; if (l <= mid) { ans = max(ans, query(ls, l, r)); } if (r > mid) { ans = max(ans, query(rs, l, r)); } return ans;}int main(){ int n, m; while (scanf("%d %d", &n, &m) == 2) { build(1, n, 1); int temp_1, temp_2; char c; while (m--) { getchar(); scanf("%c %d %d", &c, &temp_1, &temp_2); if (c == 'U') { update(1, n, 1, temp_1, temp_2); } else if (c == 'Q') { printf("%d\n", query(1, n, 1, temp_1, temp_2)); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。