HDU1754
2024-08-26 02:23:14
https://vjudge.net/contest/66989#problem/B
很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
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
Hint
Huge input,the C function scanf() will work better than cin
#include<iostream>
#include<stdio.h>
#include<string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn=;
int sum[maxn<<];
void pushup(int rt)
{
sum[rt]=max(sum[rt<<],sum[rt<<|]);
}
/*
void pushdown(int rt,int ln,int rn)
{
if(add[rt])
{
sum[rt<<1]+=add[rt]*ln;
sum[rt<<1|1]+=add[rt]*rn;
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
add[rt]=0;
}
}
*/
void build(int l,int r,int rt)
{
if(r==l)
{
scanf("%d",&sum[rt]);
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int c,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=c;
return;
}
int m=(l+r)>>;
if(L<=m)
update(L,c,lson);
else
update(L,c,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt];
}
int ans=;
int m=(r+l)>>;
if(L<=m)
ans=max(ans,query(L,R,lson));
if(R>m)
ans=max(ans,query(L,R,rson));
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,m,x,y;
char b;
while(~scanf("%d%d",&n,&m))
{
build(,n,);
for(int i=;i<=m;i++)
{
getchar();
scanf("%c%d%d",&b,&x,&y);
if(b=='Q')
printf("%d\n",query(x,y,,n,));
else
update(x,y,,n,);
}
}
return ;
}
最新文章
- mysql 卸载 linux
- DFD
- PHP Closure类Bind与BindTo方法
- generator自动生成mybatis配置和类信息
- http://www.miniui.com/demo/#src=datagrid/celledit.html
- Vs 引用第三方DLL文件 版本不一致问题 (npoi与memcached中的ICSharpCode.SharpZipLib版本冲突的解决方案)
- aspx页面状态管理Cookie和ViewState
- Html5实现头像上传和编辑,保存为Base64的图片过程
- Sumsets(POJ 2229 DP)
- Python中yield深入理解
- MySQL 创建用户与修改密码
- C++学习笔记6
- poj3254(状压dp)
- HTML与XML总结
- 如何在一个项目中同时包含mvc建站、webapi接口
- 描述一下Spring框架的作用和优点?
- DIV与SPAN之间有什么区别
- Linux必备150个命令
- Servlet工作原理解析(tomcat7、嵌入式服务器)
- 扫描工具——Nmap用法详解
热门文章
- RxJava1升级到RxJava2的注意事项
- Java 并发:Future FutureTask
- JavaScript中=、==、===以及!=、!==的区别与联系
- WebForms开发方式以及优缺点,来源《ASP.NET MVC企业级实战》
- layui 页面加载 阴影 请求页面加载转圈页面
- (1-2)line-height的各类属性值
- AngularJS学习之 ui router
- 使用ArcGIS Pro编辑在线三维服务图层
- Nodejs搭建wss服务器
- Android 2018最新的三方库