hdu1754(线段树单点替换&区间最值模板)
2024-09-08 09:59:32
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1754
题意:中文题诶~
思路:线段树单点替换&区间最大值查询模板
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std; const int MAXN = 2e5 + ;
int Max[MAXN << ];//Max[rt]存储rt对应区间的最大值 void push_up(int rt){//更新rt的值
Max[rt] = max(Max[rt << ], Max[rt << | ]);
} //建树
void build(int l, int r, int rt){//rt对应区间[l, r]
if(l == r){
scanf("%d", &Max[rt]);
return;
}
int mid = (l + r) >> ;
build(lson);
build(rson);
push_up(rt);//向上更新
} //单点替换
void updata(int p, int sc, int l, int r, int rt){//将p点值替换成sc
if(l == r){//找到p点
Max[rt] = sc;
return;
}
int mid = (l + r) >> ;
if(p <= mid) updata(p, sc, lson);
else updata(p, sc, rson);
push_up(rt);//向上更新节点
} //求区间最值
int query(int L, int R, int l, int r, int rt){//查询[L, R]内最大值
if(L <= l && R >= r) return Max[rt];//当前区间[l, r]包含在[L, R]中
int cnt = ;
int mid = (l + r) >> ;
if(L <= mid) cnt = max(cnt, query(L, R, lson));//L在mid左边
if(R > mid) cnt = max(cnt, query(L, R, rson));//R在mid右边
return cnt;
} int main(void){
int n, m;
while(~scanf("%d%d", &n, &m)){
// memset(Max, 0, sizeof(Max));
build(, n, );
char ch[];
int x, y;
while(m--){
scanf("%s%d%d", ch, &x, &y);
if(ch[] == 'U') updata(x, y, , n, );
else printf("%d\n", query(x, y, , n, ));
}
}
return ;
}
最新文章
- html+css基础知识总结
- HDU4003Find Metal Mineral[树形DP 分组背包]
- JS转码
- 构建spring+mybatis+redis架构时遇到的小异常
- 解决passwd 为普通用户设密码 不成功的方法
- ytu 1064: 输入三个字符串,按由小到大的顺序输出(水题,字符串处理)
- CSS id 选择器
- js实现table排序-sortable.js
- android下基本json串的生成与解析
- javascript的框架演化
- 学习MVC遇到的问题
- 基于python的知乎开源爬虫 zhihu_oauth使用介绍
- jvm学习记录-对象的创建、对象的内存布局、对象的访问定位
- Composer之搭建自己的包工具
- Cannot create a session after the response has been committed
- c++中的header-only library
- url override and HttpSession implements session for real
- linux 修改MTU值
- ASP.NET5之客户端开发:Grunt和Gulp构建工具在Visual Studio 2015中的高效的应用
- 大白话Docker入门(一)
热门文章
- Latex 4: WinEdt 10试用时间限制的破解+注册码激活
- Bootstrap——组件
- 在pycharm中执行脚本没有报错但输出显示Redirection is not supported.
- mysql父子查询
- HTML5_CSS3可切换注册登录表单
- SDUT OJ 1479 数据结构实验之栈:行编辑器
- Hive- Hive安装
- Ubuntu 17.4下如何安装和配置flash player
- Apache Flink vs Apache Spark——感觉二者是互相抄袭啊 看谁的好就抄过来 Flink支持在runtime中的有环数据流,这样表示机器学习算法更有效而且更有效率
- hdu-5781 ATM Mechine(dp+概率期望)