I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 28169 Accepted Submission(s): 11168
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题意:
多case输入,每个case包含N(0到200000)个人和M(0到5000)条信息。随后给出N个人的成绩。信息有两类,当为Q a b时,表示求a到b号同学成绩最高的一位,输出这个成绩;当为C a b时,表示将a同学的成绩变为b成绩。
思路:
线段树基础题。求最大值。与之前做的求和条件有点不同而已,大致一样。将结构体的总和改成最大值就好了。
AC:
#include<stdio.h> #include<string.h> #define MAX 2000000+5 typedef struct { int st; //区间起点 int en; //区间重点 int max; //区间最大值 }node; int student[MAX]; node no[MAX]; int ma; //递归建树过程 void build(int from,int to,int i) { int mid=(from+to)/2; no[i].st=from; no[i].en=to; if(from==to) { no[i].max=student[from]; return; } //当from==to的时候,只有自己的成绩,所以直接赋值就好了 build(from,mid,2*i); build(mid+1,to,2*i+1); no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max); //这个条件改了,max值是对比最大得出 } void change(int who,int grade,int i) { int mid=(no[i].st+no[i].en)/2; if(no[i].st==no[i].en&&no[i].st==who) { no[i].max=grade; return; } if(who<=mid) change(who,grade,2*i); if(who>=mid+1) change(who,grade,2*i+1); no[i].max=(no[2*i].max>no[2*i+1].max?no[2*i].max:no[2*i+1].max); //同样的,这里也为对比赋值 } void search(int from,int to,int i) { int mid=(no[i].st+no[i].en)/2; if(from==no[i].st&&to==no[i].en) { ma=(ma>no[i].max?ma:no[i].max); //这里也是对比得出 return; } if(from>=mid+1) search(from,to,2*i+1); if(to<=mid) search(from,to,2*i); if(from<=mid&&to>=mid+1) { search(from,mid,2*i); search(mid+1,to,2*i+1); } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(student,0,sizeof(student)); memset(no,0,sizeof(no)); for(int i=1;i<=n;i++) scanf("%d",&student[i]); build(1,n,1); while(m--) { char c; scanf(" %c",&c); if(c=='Q') { int from,to; scanf("%d%d",&from,&to); ma=0; search(from,to,1); printf("%d\n",ma); } if(c=='U') { int who,grade; scanf("%d%d",&who,&grade); change(who,grade,1); } } } return 0; }
14-07-19 更新 AC 代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; const int MAX = 200005; int num[MAX], tree[MAX * 5]; void build (int node, int l, int r) { int mid = l + (r - l) / 2; if (l == r) { tree[node] = num[l]; } else { build (node * 2, l, mid); build (node * 2 + 1, mid + 1, r); tree[node] = max(tree[node * 2], tree[node * 2 + 1]); } } int query (int node, int l, int r, int al, int ar) { int mid = l + (r - l) / 2; if (ar < l || al > r) return -1; else if (al <= l && ar >= r) return tree[node]; else return max( query(node * 2, l, mid, al, ar), query(node * 2 + 1, mid + 1, r, al, ar) ); } void update (int node, int l, int r, int num, int ans) { int mid = l + (r - l) / 2; if (l == r && l == num) tree[node] = ans; else { if (num <= mid) update(node * 2, l, mid, num, ans); else update(node * 2 + 1, mid + 1, r, num, ans); tree[node] = max(tree[node * 2], tree[node * 2 + 1]); } } int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } build(1, 1, n); while(m--) { char q; int a, b; scanf(" %c%d%d", &q, &a, &b); if (q == 'Q') { int ans = query(1, 1, n, a, b); printf("%d\n", ans); } else { update(1, 1, n, a, b); } } } }
相关推荐
代码
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 ...
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 ...
Build APIs You Wont Hate 2014.pdf
Emotional Design - Why we Love Or Hate everyday things
I hate the feeling that my presence doesn’t really matter and that the world would have been exactly no different in a meaningful way if my work hadn’t been done. To become remarkable, you have to ...
从mailto链接快速复制电子邮件地址 告别让您突然冒出的电子邮件客户端。 这个方便的Google Chrome和Firefox扩展程序会将电子邮件地址从mailto链接复制到剪贴板,并停止您从未使用过的默认邮件客户端。...
Stop Asian Hate! Refining Detection of Anti-Asian Hate Speech During the COVID-19 Pandemic_停止亚洲仇恨!2019冠状病毒疾病流行期间反亚裔仇恨言语的检测.pdf
语言:中文 (繁體) world.yam.com很棒,但是图片上的评论框很烦人!
《爱上统计学》英文原版! 【内容简介】 在经过不断地摸索以及少量成功大量失败的尝试之后,我已经学会了以某种方式教授统计学,我和我的许多学生认为这种方式不会让人感到害怕,同时能够传递大量的信息。...
我恨你我爱你的卸妆病毒,Delphi,20岁;)
相信很多朋友都想找的. SYBASE这东东,在WINDOWS下不好用. I HATE IT UNDER WINDOWS. 没办法,我们的ERP用的是SYBASE. SYBASE做三层就得用它了.
world.yam.com是真棒,但在图片的评论框是烦人的! 支持语言:中文 (繁體)
i hate you description
i hate your description
(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, ...