原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1754
I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 38000 Accepted Submission(s): 15035
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
Source
Recommend
分析:用线段树,把每个子区间的设置为一个子节点,节点存放改子区间的最大分数。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define MAXN 200010 int n,m,a,b; int Max[4*MAXN]; char op[5]; //查询 int query(int r,int L,int R){ int ans=-1; int M=(L+R)/2; if(a<=L&&R<=b) return Max[r]; if(b<=M) return query(r*2,L,M); else if(a>M) return query(r*2+1,M+1,R); else { ans=max(query(r*2,L,M),query(r*2+1,M+1,R)); } return ans; } //更新 void update(int r,int L,int R){ int M=(L+R)/2; if(L==R) Max[r]=b; else { if(a<=M) update(r*2,L,M);else update(r*2+1,M+1,R); Max[r]=max(Max[r*2],Max[r*2+1]); } } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=0;i<n;i++){ scanf("%d",&b); a =i+1; update(1,1,n); } for(int i=0;i<m;i++){ scanf("%s %d %d",op,&a,&b); if(op[0] =='Q'){ printf("%d\n",query(1,1,n)); } else { update(1,1,n); } } } return 0; }
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1738772
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
HDU 1022 Train Problem I 附详细思路
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类