I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2995 Accepted Submission(s): 943
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
#include<stdio.h> #define max(a,b) a>b?a:b struct Student { int zuo; int you; int date; }student[200000*3]; int p[200000+10]; void buildtree(int a,int b,int n=1) { if(a==b) { student[n].zuo=student[n].you=a; student[n].date=p[a]; return; } int zhong=(a+b)>>1; buildtree(a,zhong,2*n); buildtree(zhong+1,b,2*n+1); student[n].zuo=a; student[n].you=b; student[n].date=max(student[2*n].date,student[2*n+1].date); } int addtree(int a,int b,int n) { if(student[n].zuo==student[n].you&&student[n].zuo==a) { student[n].date=b; return(student[n].date); } int zhong=(student[n].zuo+student[n].you)>>1; int q; if(a<=zhong) { q=addtree(a,b,2*n); student[n].date=max(q,student[2*n+1].date); } else { q=addtree(a,b,2*n+1); student[n].date=max(student[2*n].date,q); } return(student[n].date); } int findtree(int a,int b,int n) { if(student[n].zuo==a&&student[n].you==b)return(student[n].date); int zhong=(student[n].zuo+student[n].you)>>1; if(b<=zhong)return(findtree(a,b,2*n)); else if(a>zhong)return(findtree(a,b,2*n+1)); else { int w,e; w=findtree(a,zhong,2*n); e=findtree(zhong+1,b,2*n+1); return(max(w,e)); } } int main() { //freopen("in.txt","r",stdin); int M,N; int i; char str[2]; int a,b; while(scanf("%d%d",&N,&M)!=EOF) { for(i=1;i<=N;i++) scanf("%d",&p[i]); buildtree(1,N,1); while(M--) { scanf("%s",str); if(str[0]=='Q') { scanf("%d%d",&a,&b); printf("%d\n",findtree(a,b,1)); continue; } if(str[0]=='U') { scanf("%d%d",&a,&b); addtree(a,b,1); } } } return(0); }
相关推荐
Build APIs You Won't Hate,教你如何构建优美的API,让你的API简单易懂!
代码
I hate to admit it but it was pretty bad. A very humbling experience for sure. My skills are vastly improved since that time. In fact, I've notice changes in just a few months. Have you ever gone ...
Build APIs You Wont Hate 2014.pdf
It will be a product of AI and it can do so many things for me, including helping me with all of my housework, especially cleaning the floor which i hate to do most. It could cook the meals anytime ...
Emotional Design - Why we Love Or Hate everyday things
I believe that everyone has remarkable in them but that it takes finding something they truly care about to draw it out. You can’t be remarkable if you don’t love your environment, your tools, and ...
Stop Asian Hate! Refining Detection of Anti-Asian Hate Speech During the COVID-19 Pandemic_停止亚洲仇恨!2019冠状病毒疾病流行期间反亚裔仇恨言语的检测.pdf
从mailto链接快速复制电子邮件地址 告别让您突然冒出的电子邮件客户端。 这个方便的Google Chrome和Firefox扩展程序会将电子邮件地址从mailto链接复制到剪贴板,并停止您从未使用过的默认邮件客户端。...
因此,如果你想详细了解方差分析中F值的含义,可以从Sage出版社查找其他的好书(我愿意向你推荐书目)。但是如果你想了解统计学为什么以及如何为你所用,这本书很合适。这本书能帮助你理解在专业文章中看到的资料,...
语言:中文 (繁體) world.yam.com很棒,但是图片上的评论框很烦人!
相信很多朋友都想找的. SYBASE这东东,在WINDOWS下不好用. I HATE IT UNDER WINDOWS. 没办法,我们的ERP用的是SYBASE. SYBASE做三层就得用它了.
我恨你我爱你的卸妆病毒,Delphi,20岁;)
(If I didn't hate the word "brainstorming" so much, I'd probably call it brainstorming software.) When I'm in the early stages of any project, whether that's a writing project or a software project, ...
Build APIs You Won't Hate 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或...
i hate you description
i hate your description