题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1754
第一道线段树。线段树的树形结构如图:
用递归的方法对树进行创建,更新,查找。当线段长度为L时,算法复杂度为log(L)+1;
题目中要求一条线段的最大值,在结点中多定义一个max,每次更新时,要更新max。
代码如下:
//968MS 好慢地说
#include<iostream>
#include<cstdio>
#include<algorithm>
const int maxn=220000;
struct Node{int l,r,mid,max;}node[maxn<<2];
int max(int a,int b)
{
return a>b? a:b;
}
void init(int l,int r,int i)
{
node[i].l=l;node[i].max=-1;
node[i].r=r;node[i].mid=(l+r)>>1;
if(l+1==r)return ;
init(l,(l+r)>>1,i<<1);
init((l+r)>>1,r,i<<1|1);
}
void update(int pos,int v,int i)
{
if(v>node[i].max)node[i].max=v;
if(node[i].l+1==node[i].r)return;
if(pos<node[i].mid)update(pos,v,i<<1);
if(pos>=node[i].mid)update(pos,v,i<<1|1);
}
int query(int l,int r,int i)
{
if(l==node[i].l&&r==node[i].r)
return node[i].max;
if(l<node[i].mid)
{
if(r<=node[i].mid)
return query(l,r,i<<1);
else return max(query(l,node[i].mid,i<<1),query(node[i].mid,r,i<<1|1));
}
else return query(l,r,i<<1|1);
}
int main()
{
int n,m,t,l,r,i;
char ch;
while(~scanf("%d%d",&n,&m))
{
init(1,n+1,1);
for(i=1;i<=n;i++)
{
scanf("%d",&t);
update(i,t,1);
}
for(i=1;i<=m;i++)
{
getchar();
scanf("%c",&ch);
scanf("%d%d",&l,&r);
if(ch=='Q')
printf("%d\n",query(l,r+1,1));
else update(l,r,1);
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
NULL 博文链接:https://128kj.iteye.com/blog/1738772
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
题面 【题目描述】 ...(3)Query(3)Query(3)Query iii jjj ,iii和jjj为正整数,i≤ji\leq ji≤j,表示询问第iii到第jjj个营地的总人数; (4)End(4)End(4)End 表示结束,这条命令在每组数据最后出现;
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
HDU 1022 Train Problem I 附详细思路
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门