热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU1754IHateIt(线段树:单点替换求最值)

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

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


Input

本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0 学生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


Author

linle

Source

2007省赛集训队练习赛(6)_linle专场

Recommend

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

题意:略。

题解:线段树单点替换求最值。




AC代码:

#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 = 1e-8;
const int INF = 1e9+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; v*10&#43;c-48, c &#61; getchar();
return v*f;}
int MAX[maxn<<2];void pushup(int rt) //把当前结点的信息更新到父结点
{//线段树是用数组来模拟树形结构//对于每一个节点rt,左子节点为 2*rt (一般写作rt<<1)右子节点为 2*rt&#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;
}




推荐阅读
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 寒假作业解析:第三周 2月12日 第7题
    尽快完成之前的练习任务!每日一练2.1 Problem A Laurenty and Shop 的题目要求是选择两条不同的路线以最小化总的等待时间。简要分析:通过对比不同路线的等待时间,可以找到最优解。此问题可以通过动态规划或贪心算法来解决,具体取决于路线的复杂性和约束条件。 ... [详细]
  • 题目链接:POJ 2777。问题描述:给定一个区域,需要进行多次涂色操作,并在每次操作后查询某个区间内的不同颜色数量。解决方案:由于题目中颜色种类不超过30种,可以利用线段树的懒惰更新策略来高效处理这些操作。通过懒惰标记,避免了不必要的节点更新,从而显著提高了算法的效率。此外,该方法还能有效应对大规模数据输入,确保在合理的时间内完成所有操作。 ... [详细]
  • 在探讨 MySQL 正则表达式 REGEXP 的功能与应用之前,我们先通过一个小实验来对比 REGEXP 和 LIKE 的性能。通过具体的代码示例,我们将评估这两种查询方式的效率,以确定 REGEXP 是否值得深入研究。实验结果将为后续的详细解析提供基础。 ... [详细]
  • Squaretest:自动生成功能测试代码的高效插件
    本文将介绍一款名为Squaretest的高效插件,该工具能够自动生成功能测试代码。使用这款插件的主要原因是公司近期加强了代码质量的管控,对各项目进行了严格的单元测试评估。Squaretest不仅提高了测试代码的生成效率,还显著提升了代码的质量和可靠性。 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 本文详细介绍了使用 Python 进行 MySQL 和 Redis 数据库操作的实战技巧。首先,针对 MySQL 数据库,通过 `pymysql` 模块展示了如何连接和操作数据库,包括建立连接、执行查询和更新等常见操作。接着,文章深入探讨了 Redis 的基本命令和高级功能,如键值存储、列表操作和事务处理。此外,还提供了多个实际案例,帮助读者更好地理解和应用这些技术。 ... [详细]
  • 本文探讨了如何利用 jQuery 的 JSONP 技术实现跨域调用外部 Web 服务。通过详细解析 JSONP 的工作原理及其在 jQuery 中的应用,本文提供了实用的代码示例和最佳实践,帮助开发者解决跨域请求中的常见问题。 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 在Kohana 3框架中,实现最优的即时消息显示方法是许多开发者关注的问题。本文将探讨如何高效、优雅地展示flash消息,包括最佳实践和技术细节,以提升用户体验和代码可维护性。 ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 解析 /etc/pki/tls/certs/cabundle.crt 文件的主要功能与应用场景 ... [详细]
  • 蓝桥杯算法实战:节点选取策略优化分析
    本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果,提出了基于贪心算法和动态规划的综合优化方案,旨在提高算法效率和准确性。实验结果表明,该优化策略在处理大规模数据集时表现出色,显著提升了算法性能。 ... [详细]
  • 在Android 4.4系统中,通过使用 `Intent` 对象并设置动作 `ACTION_GET_CONTENT` 或 `ACTION_OPEN_DOCUMENT`,可以从相册中选择图片并获取其路径。具体实现时,需要为 `Intent` 添加相应的类别,并处理返回的 Uri 以提取图片的文件路径。此方法适用于需要从用户相册中选择图片的应用场景,能够确保兼容性和用户体验。 ... [详细]
  • 开发心得:成为SGU475智能筏工的策略与技巧 ... [详细]
author-avatar
哈罗xeh_406
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有