当前位置: 开发笔记 > 编程语言 > 正文

HDU1754IHateIt（线段树：单点替换求最值）

作者：哈罗xeh_406 | 来源：互联网 | 2023-10-12 18:01

IHateItTimeLimit:90003000MS(JavaOthers)MemoryLimit:3276832768K(JavaOthers)TotalSubmission

I Hate It
Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 66254    Accepted Submission(s): 25769

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问&＃xff0c;从某某到某某当中&＃xff0c;分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢&＃xff0c;现在需要你做的是&＃xff0c;就是按照老师的要求&＃xff0c;写一个程序&＃xff0c;模拟老师的询问。当然&＃xff0c;老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试&＃xff0c;请处理到文件结束。
在每个测试的第一行&＃xff0c;有两个正整数 N 和 M ( 0 学生ID编号分别从1编到N。
第二行包含N个整数&＃xff0c;代表这N个学生的初始成绩&＃xff0c;其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取&＃39;Q&＃39;或&＃39;U&＃39;) &＃xff0c;和两个正整数A&＃xff0c;B。
当C为&＃39;Q&＃39;的时候&＃xff0c;表示这是一条询问操作&＃xff0c;它询问ID从A到B(包括A,B)的学生当中&＃xff0c;成绩最高的是多少。
当C为&＃39;U&＃39;的时候&＃xff0c;表示这是一条更新操作&＃xff0c;要求把ID为A的学生的成绩更改为B。

Output

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

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

Author

linle

Source

2007省赛集训队练习赛&＃xff08;6&＃xff09;_linle专场

Recommend

lcy   |   We have carefully selected several similar problems for you:  1542 2795 1540 1255 1828

题意&＃xff1a;略。

题解&＃xff1a;线段树单点替换求最值。

AC代码&＃xff1a;

#pragma comment(linker, "/STACK:102400000,102400000") //#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef vector vi; const double eps &＃61; 1e-8; const int INF &＃61; 1e9&＃43;7; const ll inf &＃61;(1LL<<62) ; const int MOD &＃61; 1e9 &＃43; 7; const ll mod &＃61; (1LL<<32); const int N &＃61;1e6&＃43;6; const int M&＃61;100010; const int maxn&＃61;200010; #define mst(a) memset(a, 0, sizeof(a)) #define M_P(x,y) make_pair(x,y) #define in freopen("in.txt","r",stdin) #define rep(i,j,k) for (int i &＃61; j; i <&＃61; k; i&＃43;&＃43;) #define per(i,j,k) for (int i &＃61; j; i >&＃61; k; i--) #define lson l , mid , rt <<1 #define rson mid &＃43; 1 , r , rt <<1 | 1 const int lowbit(int x) { return x&-x; } //const int lowbit(int x) { return ((x)&((x)^((x)-1))); } int read(){ int v &＃61; 0, f &＃61; 1;char c &＃61;getchar(); while( c <48 || 57 while(48 <&＃61; c && c <&＃61; 57) v &＃61; v10&＃43;c-48, c &＃61; getchar(); return vf;} int MAX[maxn<<2];void pushup(int rt) //把当前结点的信息更新到父结点 {//线段树是用数组来模拟树形结构//对于每一个节点rt,左子节点为 2rt (一般写作rt<<1)右子节点为 2rt&＃43;1&＃xff08;一般写作rt<<1|1&＃xff09; MAX[rt] &＃61; max(MAX[rt<<1] , MAX[rt<<1|1]); } void build(int l,int r,int rt) {if(l&＃61;&＃61;r){scanf("%d",&MAX[rt]); return;}int mid&＃61;(l&＃43;r)>>1;build(lson);//递归构造左子树build(rson);//递归构造右子树pushup(rt); //更新求和 } void update(int p, int change, int l, int r, int rt)//单点替换 {if(l&＃61;&＃61;r){MAX[rt] &＃61; change; return ;}int mid&＃61;(l&＃43;r) >> 1;if(p<&＃61;mid) update(p,change,lson);else update(p,change,rson);pushup(rt); } int query(int L,int R,int l,int r,int rt) //区间最值 {if(L <&＃61; l && r <&＃61; R){return MAX[rt];}int mid &＃61; (l&＃43;r)>>1;int ans &＃61; 0;if(L <&＃61; mid) ans&＃61;max(ans,query(L,R,lson));if(R > mid) ans&＃61;max(ans,query(L,R,rson));return ans; } int main() {int n,m;while(~scanf("%d%d",&n,&m)){build(1,n,1);while(m--){char op[3];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0]&＃61;&＃61;&＃39;Q&＃39;)printf("%d\n",query(a,b,1,n,1));else update(a,b,1,n,1);}}return 0; }

推荐阅读

include
最小路径覆盖与强连通分量的应用：国王的问题

本题探讨了在一个有向图中，如何根据特定规则将城市划分为若干个区域，使得每个区域内的城市之间能够相互到达，并且划分的区域数量最少。题目提供了时间限制和内存限制，要求在给定的城市和道路信息下，计算出最少需要划分的区域数量。 ... [详细]

蜡笔小新 2024-12-23 18:42:12
int
解析 org.apache.commons.io.IOCase.checkCompareTo() 方法及其应用

本文详细介绍了 org.apache.commons.io.IOCase 类中的 checkCompareTo() 方法，通过多个代码示例展示其在不同场景下的使用方法。 ... [详细]

蜡笔小新 2024-12-23 15:32:05
include
递推算法与大数处理

本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]

蜡笔小新 2024-12-23 12:18:55
int
JavaScript 基础语法指南

本文详细介绍了 JavaScript 的基础语法，包括变量、数据类型、运算符、语句和函数等内容，旨在为初学者提供全面的入门指导。 ... [详细]

蜡笔小新 2024-12-23 10:54:44
int
Servlet 表单处理：GET 和 POST 请求的深入解析

本文详细探讨了HTML表单中GET和POST请求的区别，包括它们的工作原理、数据传输方式、安全性及适用场景。同时，通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]

蜡笔小新 2024-12-23 18:09:59
int
实现页面自动加载更多内容功能：类微博和Pinterest的设计

在现代Web应用中，当用户滚动到页面底部时，自动加载更多内容的功能变得越来越普遍。这种无刷新加载技术不仅提升了用户体验，还优化了页面性能。本文将探讨如何实现这一功能，并介绍一些实际应用案例。 ... [详细]

蜡笔小新 2024-12-23 17:01:04
include
如何高效清空C++标准输入缓冲区

本文探讨了在C++中如何有效地清空输入缓冲区，确保程序只处理最近的输入并丢弃多余的输入。我们将介绍一种不阻塞的方法，并提供一个具体的实现方案。 ... [详细]

蜡笔小新 2024-12-23 15:44:01
int
理解反向投影技术及其应用

反向投影技术主要用于在大型输入图像中定位特定的小型模板图像。通过直方图对比，它能够识别出最匹配的区域或点，从而确定模板图像在输入图像中的位置。 ... [详细]

蜡笔小新 2024-12-23 12:24:22
include
树链问题的优化解法：深度优先搜索与质因数分解

本文介绍了一种通过深度优先搜索（DFS）和质因数分解来解决最长树链问题的方法。我们通过枚举树链上的最大公约数（GCD），将所有节点按其质因子分类，并计算每个类别的最长链，最终求得全局最长链。 ... [详细]

蜡笔小新 2024-12-23 11:59:34
include
括号序列的最小合法化：区间动态规划与路径记录

问题描述：通过添加最少数量的括号，使得给定的括号序列变为合法，并输出最终的合法序列。数据范围：字符串长度不超过100。涉及算法：区间动态规划（Interval DP）。 ... [详细]

蜡笔小新 2024-12-23 11:50:27
int
PHP 实现网页内容抓取及数据解析

本文由杨勇和思远于2012年12月27日撰写，主要探讨了如何使用PHP进行网页内容抓取，特别是针对字符较多的网站。文章详细介绍了正则表达式失效的原因，并提供了优化方法，同时展示了如何抓取淘宝服饰栏、天气信息以及IP地址对应的地理位置。 ... [详细]

蜡笔小新 2024-12-23 11:27:18
int
Android 自定义绘图板应用

本文介绍如何使用 Android 的 Canvas 和 View 组件创建一个简单的绘图板应用程序，支持触摸绘画和保存图片功能。 ... [详细]

蜡笔小新 2024-12-23 10:12:53
include
iBatis.NET 循环迭代：深入解析 Iterate 标签

本文详细介绍了 iBatis.NET 中的 Iterate 元素，它用于遍历集合并重复生成每个项目的主体内容。通过该元素，可以实现类似于 foreach 的功能，尽管 iBatis.NET 并未直接提供 foreach 标签。 ... [详细]

蜡笔小新 2024-12-23 18:51:40
int
深入解析Redis内存对象模型

本文详细介绍了Redis内存对象模型的关键知识点，包括内存统计、内存分配、数据存储细节及优化策略。通过实际案例和专业分析，帮助读者全面理解Redis内存管理机制。 ... [详细]

蜡笔小新 2024-12-23 14:50:23
include
性能对比：Jsonapi-rb与AMS

本文探讨了Jsonapi-rb与ActiveModelSerializers (AMS)在性能上的差异，并分享了详细的基准测试结果。 ... [详细]

蜡笔小新 2024-12-23 10:11:22

哈罗xeh_406

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章