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)


相关推荐

  • eidos云矿机_空投挖矿

    eidos云矿机_空投挖矿eidos空投矿机虽然已经有几款网页版的了,甚至还有收费的,但并不适合长期运行,特别是需要挂在VPS里,所以就出现了这款控制台运行的,如果觉得对你有帮助就给个star吧。项目地址https://github.com/donjan-deng/eidos-miner环境需求nodejs>=10scatter>=11(网页版可在低版本运行)使用方法也有个简易的网页版…

  • dede 提交表单 发送邮件

    dede 提交表单 发送邮件

  • Android代码混淆官方实现方法「建议收藏」

    Android代码混淆官方实现方法「建议收藏」首先查看一下“project.properties”这个文件:#ThisfileisautomaticallygeneratedbyAndroidTools.#Donotmodifythisfile–YOURCHANGESWILLBEERASED!##ThisfilemustbecheckedinVersionContro

  • linux图形界面扩容lvm,linux下对LVM扩容

    linux图形界面扩容lvm,linux下对LVM扩容操作环境:VirtualBox下RedHat6.464位版本扩容原因:/dev/vg_rhel64/lv_root占用率达到100%,导致部分应用无法继续运行操作过程:1.关闭系统,在虚拟机中添加一块10G的磁盘2.查看新添加磁盘对应的名称[root@rhel64~]#fdisk-cul得知磁盘对应名称为/dev/sdc3.给sdc分区,只分一个区sdc1[root@rhel64…

  • apt 与 dpkg[通俗易懂]

    apt 与 dpkg[通俗易懂]dpkg简介“dpkg”是“DebianPackager”的简写。为“Debian”专门开发的套件管理系统,方便软件的安装、更新及移除。所有源自“Debian”的“Linux”发行版都使用“dpkg”,例如“Ubuntu”、“Knoppix”等。dpkg是Debian软件包管理器的基础,它被伊恩·默多克创建于1993年。dpkg与RPM十分相似,同样被用于安装、卸载和供给….

  • 浅析Python优势所在

    浅析Python优势所在浅析Python优势所在 Python优势的最大有点就是比其他语言更简单易学,功能强大的解释型编程语言,它有简洁明了的语法,高效率的高层数据结构,能够简单而有效地实现面向对象编程,欢迎大家学习参考。如果你仅仅认为用Python优势只能写写“HelloWorld”,那你就大错特错了。Python可以被应用到网络开发、GUI开发、图形开发、Web开发、游戏开发、手机

发表回复

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

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