B – I Hate It

B – I Hate It

B – I Hate It

B – I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 
这让很多学生很反感。 

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

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。 

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

这题也是基本的线段树,在上一题的基础上,多了一个求节点最大值的函数,并且把query的查找函数的功能由求这一区间的和改为求这一区间的最大值,中间也一直错,还好现在对线段树的基本代码是熟练了

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const  int maxn =  200000+100;
int tree[maxn*4],ae[maxn];
void zuida(int node)
{
	tree[node] = max(tree[node*2],tree[node*2+1]);
}
void build(int node, int l, int r)
{
	if(l==r)
	{
		tree[node]=ae[l];
		return ;
	}
	int mid =(l + r)/ 2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
	tree[node]=tree[node*2]+tree[node*2+1];
	zuida(node);
}
void update(int x,int indx,int node, int l, int r)
{
	if(l==r)
	{
		tree[node]=x;
		return ;
	}
	int mid=(l+r)/2;
	if(indx<=mid)  update(x,indx,node*2,l,mid);
	if(indx>mid) update(x,indx,node*2+1,mid+1,r);
	tree[node]=tree[node*2]+tree[node*2+1];
	zuida(node);
}
int query(int x,int y,int node,int l, int r)
{
	if(x<=l&&y>=r)
	{
		return tree[node];
	}
	int mid = (l+r)/2;
	int sum=0;//zaizhe1liangbian
	if(x<=mid) sum=max(sum,query(x, y, node*2,l,mid));
	if(y>mid)  sum=max(sum,query(x, y, node*2+1,mid+1,r));
	return sum;
}
int main()
{
	int m, n;
	int a, b;
	while(cin>>n>>m){
	for(int i=1; i<=n; i++)  scanf("%d",&ae[i]);
	build(1,1,n);
	char s[maxn];
	while(m--)
	{
		scanf("%s",s);
		getchar();
		scanf("%d %d",&a,&b);
		if(s[0]=='Q')
		{
			printf("%d\n",query(a,b,1,1,n));
		}
		if(s[0]=='U')	update(b,a,1,1,n);
		
	}
	}
	return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114889.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • angular指令笔记(一):ng-options

    angular指令笔记(一):ng-options

  • 矩阵分解模型

    矩阵分解模型矩阵分解模型做如下假设:1.每个用户可描述为n个属性或特征。比如,第一个特征可以对应某个用户对动作片的喜好程度。2.每个物品可描述为n个属性或特征。比如,接上一点,第一个特征可以用对应某部电影与动作片的接近程度。3.将用户和物品对应的属性相乘后求和,该值可能很接近用户会对该物品的评级。 1.显式矩阵分解当要处理的数据是由用户所提供的自身的偏好数据时,这些数据被称作显式偏好数…

  • 巧用es6数组方法,求两数组的差集!

    巧用es6数组方法,求两数组的差集!复制代码从arr1中。根据arr2中所有的项,排除过滤掉arr2中的项。letarr1=[{id:1,num:50,text:’1111111111′},{id:2,num:100,text:’222222222′},{…

  • 哈理工 oj 2122 旅行(map + 最短路dij算法)

    哈理工 oj 2122 旅行(map + 最短路dij算法)旅行TimeLimit:1000MSMemoryLimit:32768KTotalSubmit:18(6users)TotalAccepted:3(3users)Rating:SpecialJudge:NoDescription“04.24,和Sakur

  • 80X86汇编小站_z80汇编语言

    80X86汇编小站_z80汇编语言[序言]为了保证文章的质量和内容的聚合,因此博客的技术文章全部搬迁至如下网址:技术博客:http://blog.csdn.net/Code_GodFather80x86汇编小站:http://www.x86asm.com/[感谢]非常感谢多年来对我的支持,我会尽我最大的努力维护好博客的内容以及80×86汇编小站.

    2022年10月13日
  • JS实现图片循环滚动

    JS实现图片循环滚动之前在前端的时候有遇到这样一个问题,实现JS图片的循环滚动,然后鼠标移入的时候停止滚动,鼠标移开继续滚动,这里无非就是设置了一个定时器,鼠标移上时清除定时器达到滚动停止的目的,鼠标移开时重设定时器,代码如下:<!DOCTYPE><html> <head> <metacharset=”UTF-8″> <title>JS实…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号