I hate it (最值单点修改区间查询)
发布日期:2021-07-14 01:03:47 浏览次数:85 分类:技术文章

本文共 1945 字,大约阅读时间需要 6 分钟。

传送门

描述

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

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

输入

本题目包含多组测试,请处理到文件结束。

在每个测试的第一行,有两个正整数 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。

输出

对于每一次询问操作,在一行里面输出最高成绩。

样例

  • 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
  • Output
    5
    6
    5
    9

思路

  • 最值单点修改区间查询

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
#include
#include
#include
#define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) using namespace std; struct Tree{
int num,l,r; }tree[1000007]; void build(int l,int r,int d){
tree[d]=(Tree){
-1000,l,r}; if(l==r)return ; int mid=(tree[d].l+tree[d].r)/2; build(l,mid,d<<1); build(mid+1,r,d<<1|1); } void update(int a,int b,int d){
if(tree[d].l==tree[d].r){
tree[d].num=b; return; } int mid=(tree[d].l+tree[d].r)/2; if(a<=mid) update(a,b,d<<1); else update(a,b,d<<1|1); tree[d].num=max(tree[d<<1].num,tree[d<<1|1].num); } int find(int l,int r,int d){
if(tree[d].l==l&&tree[d].r==r) return tree[d].num; int mid=(tree[d].l+tree[d].r)/2; if(r<=mid) return find(l,r,d<<1); else if(l>mid) return find(l,r,d<<1|1); else return max(find(l,mid,d<<1),find(mid+1,r,d<<1|1)); } int main(){
int n,m,tem; while(~scanf("%d %d",&n,&m)){
build(1,n,1); for(int i=1;i<=n;i++){
scanf("%d",&tem); update(i,tem,1); } char s[5]; int x,y; while(m--){
scanf("%s",s); scanf("%d %d",&x,&y); if(s[0]=='Q') printf("%lld\n",find(x,y,1)); else update(x,y,1); } } return 0; }

转载地址:https://blog.csdn.net/cpongo3/article/details/89334318 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:没有上司的舞会
下一篇:石子合并

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月02日 18时53分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql 怎样链接jdbc_jdbc怎么链接mysql数据库 2019-04-21
mysql学生课程表试题_Mysql练习之 学生表、课程表 、教师表、成绩表 50道练习题... 2019-04-21
java exec封装_Java 执行系统命令工具类(commons-exec) 2019-04-21
php sha512解密,PHP加密函数 sha256 sha512 sha256_file() sha512_file() 2019-04-21
mysql里可以用cube吗_sql server的cube操作符使用详解_mysql 2019-04-21
php mysql 图书_使用PHP+MySQL来对图书管理系统进行构建 2019-04-21
单片机c语言 int1,51单片机into、int1中断计数c语言源程序.doc 2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc 2019-04-21
c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
c51写c语言外部ram头文件,C51中访问外部RAM的方法 2019-04-21
51c语言产生随机证书,基于51单片机的随机数产生器设计-LCD1602-KEY-(电路图+程序源码)... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
c语言打开一个html文件路径,C语言文件处理-C语言文件的打开和关闭 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21
Android多个签名,【Android】Android批量重签名 2019-04-21
html unicode编码转换,JS实现的Unicode编码转换操作示例 2019-04-21
html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21
html图片水平居中,CSS制作图片水平垂直居中 2019-04-21
水滴pin安卓版apk_财务报销管理系统 2019-04-21
平面设计师okr_设计团队的KPI/OKR如何制定? 2019-04-21