首页 > 代码库 > 【HDU】1754 I hate it ——线段树 单点更新 区间最值
【HDU】1754 I hate it ——线段树 单点更新 区间最值
I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 37448 Accepted Submission(s): 14816
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取‘Q‘或‘U‘) ,和两个正整数A,B。
当C为‘Q‘的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为‘U‘的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 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
Hint
Huge input,the C function scanf() will work better than cin
Author
linle
题解:很明显,这是一道线段树的单点更新求区间最值的一道题,单点更新倒是十分好办的,使用update函数更新到单点就可以了,关键是这个求区间最值的问题,假若最后查询的时候再计算这个最值,所花费的时间恐怕比直接暴力费时还要多,所以这题的正确解决方法是在update的时候顺便更新所有经过的节点的值。
AC代码如下:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int LEN = 200020; 7 8 struct line 9 {10 int left;11 int right;12 int ma;13 }line[LEN*5];14 15 void buildt(int l, int r, int step) //建树,同时初始化区间最值16 {17 line[step].left = l;18 line[step].right = r;19 line[step].ma = 0;20 if (l == r)21 return;22 int mid = (l + r) / 2;23 buildt(l, mid, step*2);24 buildt(mid+1, r, step*2+1);25 }26 27 int update(int l, int r, int value, int step) //更新函数,返回整型28 {29 if (line[step].left == line[step].right){ //如果到达最深处的节点,则说明找到了需要更新的单点,赋值30 line[step].ma = value;31 return max(line[step/2*2].ma, line[step/2*2+1].ma); //返回该节点与其兄弟节点的较大值32 }33 int mid = (line[step].left + line[step].right) / 2; //向下继续搜索34 if (r <= mid)35 line[step].ma = update(l, r, value, step*2);36 else if (l > mid)37 line[step].ma = update(l, r, value, step*2+1);38 else{ //如果目标线段处于目前线段的中点的两边,则同时搜索该节点的两个子节点,并取较大值39 line[step].ma = max(update(l, mid, value, step*2), update(mid+1, r, value, step*2+1));40 }41 return max(line[step/2*2].ma, line[step/2*2+1].ma); //返回该节点与其兄弟节点的较大值42 }43 44 int dfs(int l, int r, int step) //dfs找答案45 {46 if (l == line[step].left && r == line[step].right) //如果找到目标区间,返回值47 return line[step].ma;48 int mid = (line[step].left + line[step].right) / 2;49 if (r <= mid)50 return dfs(l, r, step*2);51 else if (l > mid)52 return dfs(l, r, step*2+1);53 else{54 return max(dfs(l, mid, step*2), dfs(mid+1, r, step*2+1)); //返回该节点与其兄弟节点的较大值55 }56 }57 58 59 int main()60 {61 int n, m;62 //freopen("in.txt", "r", stdin);63 while(scanf("%d %d", &n, &m) != EOF){64 buildt(1, n, 1);65 for(int i = 1; i <= n; i++){66 int t;67 scanf("%d", &t);68 update(i, i, t, 1);69 }70 for(int i = 0; i < m; i++){71 char query[2];72 int a, b;73 scanf("%s %d %d", query, &a, &b);74 if (query[0] == ‘U‘)75 update(a, a, b, 1);76 else if (query[0] == ‘Q‘){77 printf("%d\n", dfs(a, b, 1));78 }79 }80 }81 return 0;82 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。