首页 > 代码库 > NBUT 1434 hdu1754 I Hate It
NBUT 1434 hdu1754 I Hate It
给人的感觉真是想题目一样,woc, I Hate It ,敲完以后提交到hdu上就是过不了,硬是找了好长时间的bug,后来才知道hdu 的judge error ,转到NBUT 上才AC
吐槽毕,归于正传
Description
-
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。 - 输入
-
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 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。 - 输出
-
对于每一次询问操作,在一行里面输出最高成绩。
- 样例输入
-
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
- 样例输出
-
5 6 5 9
题意很简单,即单点更新,区间查询!
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> using namespace std; const int maxn=200005; int a[maxn]; struct node { int l,r; int CC; }tree[maxn*4]; void build_tree(int root,int l,int r) { tree[root].l=l; tree[root].r=r; if(l==r) { tree[root].CC=a[l]; return; } int mid=(l+r)/2; build_tree(root*2,l,mid); build_tree(root*2+1,mid+1,r); tree[root].CC=max(tree[root*2].CC,tree[root*2+1].CC); } void update(int root,int where,int value) { int a,b,mid; a=tree[root].l; b=tree[root].r; if(where==a&&where==b) { tree[root].CC=value; return; } mid=(a+b)>>1; if(where<=mid) update(root*2,where,value); else update(root*2+1,where,value); tree[root].CC=max(tree[root*2].CC,tree[root*2+1].CC); } int query(int root,int x,int y) { int a,b,mid; a=tree[root].l; b=tree[root].r; if(a>=x&&b<=y) return tree[root].CC; mid=(a+b)>>1; int res=-999; if(x<=mid) res=max(res,query(root*2,x,y)); if(y>=mid+1) res=max(res,query(root*2+1,x,y)); return res; } int main() { int n,m,p,q; char s[5]; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } build_tree(1,1,n); while(m--) { scanf("%s%d%d",s,&p,&q); if(s[0]==‘Q‘) printf("%d\n",query(1,p,q)); if(s[0]==‘U‘) update(1,p,q); } } return 0; }
NBUT 1434 hdu1754 I Hate It
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。