首页 > 代码库 > 洛谷 P1531 I Hate It
洛谷 P1531 I Hate It
题目背景
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。
题目描述
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩
输入输出格式
输入格式：
第一行，有两个正整数 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‘的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。
输出格式：
对于每一次询问操作，在一行里面输出最高成绩
输入输出样例
输入样例#1：
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
输出样例#1：
5659
线段树
屠龙宝刀点击就送
#include <cstdio>#define Max 200000#define max(a,b) a>b?a:bstruct node{ int l,r,dis;}tr[Max*4+1];int N,M,maxn;void up(int k){ tr[k].dis=max(tr[k<<1].dis,tr[k<<1|1].dis); }void build(int k,int l,int r){ tr[k].l=l;tr[k].r=r; if(l==r) { scanf("%d",&tr[k].dis); return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); }void section_query(int k,int l,int r){ if(tr[k].l==l&&tr[k].r==r) { maxn=max(maxn,tr[k].dis); return; } int mid=(tr[k].l+tr[k].r)>>1; if(l>mid) section_query(k<<1|1,l,r); else if(r<=mid) section_query(k<<1,l,r); else { section_query(k<<1,l,mid); section_query(k<<1|1,mid+1,r); }}void single_change(int k,int t,int v){ if(tr[k].l==tr[k].r) { tr[k].dis<v?tr[k].dis=v:tr[k].dis=tr[k].dis; return; } int mid=(tr[k].l+tr[k].r)>>1; if(mid>=t) single_change(k<<1,t,v); else single_change(k<<1|1,t,v); up(k);}int main(){ scanf("%d%d",&N,&M); build(1,1,N); char ch[4]; for(int x,y;M--;) { scanf("%s",ch+1); if(ch[1]==‘Q‘) { scanf("%d%d",&x,&y);maxn=-1;section_query(1,x,y); printf("%d\n",maxn); } else scanf("%d%d",&x,&y),single_change(1,x,y); } return 0;}
洛谷 P1531 I Hate It
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。