【hdu】I Hate It(线段树,结点修改求区间最大值)

2024-09-07 23:48

本文主要是介绍【hdu】I Hate It(线段树,结点修改求区间最大值),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

线段树的模板题,还是二分递归。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long LL;
#define MAXD 10
#define maxn 200010
int n;
int tree[maxn << 2];
void BuildTree(int l,int r,int pos){   //递归建树if(l == r){scanf("%d",&tree[pos]);return ;}int m = (l + r) >> 1;BuildTree(l,m,(pos << 1));BuildTree(m + 1,r,(pos << 1)|1);tree[pos] = max(tree[pos << 1] , tree[(pos << 1) | 1]);return ;
}
void UpDate(int aim,int value,int l,int r,int pos){  //目标结点,当前区间长度,当前结点编号if(l == r){tree[pos] = value;return ;}int m = (l + r) >> 1;if(aim <= m) UpDate(aim,value,l,m,pos << 1);elseUpDate(aim,value,m + 1, r,(pos << 1)|1);tree[pos] = max(tree[pos << 1] , tree[(pos << 1)|1]);return ;
}
int Query(int L,int R,int l,int r,int pos){if(L <= l && r <= R)return tree[pos];int m = (l + r) >> 1;int ans = -1;if(L <= m)ans = max(ans,Query(L,R,l,m,pos << 1));if(m + 1 <= R)ans = max(ans,Query(L,R,m + 1, r, (pos << 1)|1));return ans;
}
int main(){int m;while(scanf("%d%d",&n,&m) != EOF){BuildTree(1,n,1);char str[MAXD];for(int i = 0 ; i < m ; i++){scanf("%s",str);if(str[0] == 'Q'){int a,b;scanf("%d%d",&a,&b);int ans = Query(a,b,1,n,1);printf("%d\n",ans);}else if(str[0] == 'U'){int a,b;scanf("%d%d",&a,&b);UpDate(a,b,1,n,1);}}}return 0;
}

这篇关于【hdu】I Hate It(线段树,结点修改求区间最大值)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146514

相关文章

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Linux修改pip临时目录方法的详解

《Linux修改pip临时目录方法的详解》在Linux系统中,pip在安装Python包时会使用临时目录(TMPDIR),但默认的临时目录可能会受到存储空间不足或权限问题的影响,所以本文将详细介绍如何... 目录引言一、为什么要修改 pip 的临时目录?1. 解决存储空间不足的问题2. 解决权限问题3. 提

Linux文件名修改方法大全

《Linux文件名修改方法大全》在Linux系统中,文件名修改是一个常见且重要的操作,文件名修改可以更好地管理文件和文件夹,使其更具可读性和有序性,本文将介绍三种在Linux系统下常用的文件名修改方法... 目录一、引言二、使用mv命令修改文件名三、使用rename命令修改文件名四、mv命令和rename命

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》:本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1:修改配置文件方法2:hFvEWEostnamectl命

Git如何修改已提交人的用户名和邮箱

《Git如何修改已提交人的用户名和邮箱》文章介绍了如何修改Git已提交人的用户名和邮箱,包括注意事项和具体步骤,确保操作正确无误... 目录git修改已提交人的用户名和邮箱前言第一步第二步总结git修改已提交人的用户名和邮箱前言需注意以下两点内容:需要在顶层目录下(php就是 .git 文件夹所在的目

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数

修改若依框架Token的过期时间问题

《修改若依框架Token的过期时间问题》本文介绍了如何修改若依框架中Token的过期时间,通过修改`application.yml`文件中的配置来实现,默认单位为分钟,希望此经验对大家有所帮助,也欢迎... 目录修改若依框架Token的过期时间修改Token的过期时间关闭Token的过期时js间总结修改若依

MySQL修改密码的四种实现方式

《MySQL修改密码的四种实现方式》文章主要介绍了如何使用命令行工具修改MySQL密码,包括使用`setpassword`命令和`mysqladmin`命令,此外,还详细描述了忘记密码时的处理方法,包... 目录mysql修改密码四种方式一、set password命令二、使用mysqladmin三、修改u