//HDOJ 1754 I Hate It 线段树:单点替换 成求段最值
/*
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1754
题目大意:有n(0<n<=200000)个学生,已知每个学生的初始成绩。
有m(0<m<5000)次操作: 1、将a学生的成绩改为b;
2、查询区间[a,b]中成绩最高的
思路:线段树叶子结点记录每个学生的成绩,父亲结点记录其两个子孩子中较高的成绩,这样根节点记录的就是所有成绩中最
高的。更新操作从根结点开始查找,一定在左孩子或右孩子其中一个,查询后替换,然后往上更新父结点。查询操作和敌兵布
阵一样,直至记录答案的时候不是累加结果,而是去更大的值,同样递归实现,时间复杂度O(logn);
*/
#include <stdio.h>
#define root 1
#define MAXN 600000
int n,m,x,y,a[MAXN];
int Max(int a,int b){
return a>b?a:b;
}
struct node
{
int left;
int right;
int max;
}t[MAXN];
int build(int p,int left,int right)
{
t[p].left = left;
t[p].right = right;
if (left == right)
return t[p].max = a[left];
int m=(left+right)/2;
return t[p].max = Max(build(p*2, left, m),build(p*2+1, m+1, right));
}
int query(int p, int left ,int right)
{
if (t[p].left==left && t[p].right==right)
return t[p].max;
int m=(t[p].left+t[p].right)/2;
if (right<=m)
return query(p*2,left,right);
if (left>m)
return query(p*2+1,left,right);
return Max(query(p*2,left,m),query(p*2+1,m+1,right));
}
void update(int p,int x,int y)
{
if (t[p].left == t[p].right)
t[p].max=y;
else
{
int m = (t[p].left+t[p].right) / 2;
if(x<=m){
update(p*2,x,y);
t[p].max=Max(t[p].max,t[p*2].max);
}
else{
update(p*2+1,x,y);
t[p].max=Max(t[p].max,t[p*2+1].max);
}
}
}
int main()
{
int i;
char c;
while(scanf("%d %d",&n,&m)==2)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
getchar();
build(root,1,n);
while(m--){
scanf("%c %d %d",&c,&x,&y);
getchar();
if(c=='Q')
printf("%d\n",query(root,x,y));
else
update(root,x,y);
}
}
return 0;
}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc