题目名称 58. 延绵的山峰
输入输出 climb.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 512 MB
测试数据 10 简单对比
题目来源 郭家宝 2008-07-10
开放分组 全部用户
提交状态
分类标签
稀疏表 线段树 RMQ ST表
通过:394, 提交:1413, 通过率:27.88%
GravatarkZime 100 0.035 s C++
GravatarHzyuer 100 0.056 s C++
GravatarHzyuer 100 0.062 s C++
Gravatardateri 100 0.074 s C++
GravatarJobs.T 100 0.079 s C++
GravatarJobs.T 100 0.081 s C++
GravatarHzoi_Mafia 100 0.091 s C++
Gravatarsd 100 0.091 s C++
GravatarSamle 100 0.093 s C++
GravatarAHOI_521 100 0.093 s C++
关于 延绵的山峰 的讨论
ST算法适合数据个数不是特别多,但是查询很多。线段树时候数据多,但是查询少。
GravatarBYVoid
2009-04-10 21:06 1楼
……裸体吧这题……
线段树做RMQ,注意下常数优化。
Gravatar吴  豪
2009-05-02 10:12 2楼
腺哥不会线段树
GravatarEzoi_XY
2013-03-17 17:03 3楼
果的线段树,居然卡内存= =
Gravatarcstdio
2013-04-08 21:28 4楼
zkw式线段树就是快。…= =
GravatarFrCsKOH
2013-04-25 22:00 5楼
最水的算法居然过了九个点!!!!
Gravatarranto
2013-10-23 18:17 6楼
快速读入+线段树,果断时间最快(确实内存不小)
GravatarOI永别
2014-04-15 21:25 7楼
写得太丑陋,第一道RMQ。逗比无数次。
GravatarOIdiot
2014-07-06 11:27 8楼
我线段树居然开了100000 00个节点才过。。。。。。是不是我的写法有问题啊
GravatarHouJikan
2014-08-23 13:38 9楼
鄙视zkw = =
Gravatar꧁༈saber༈꧂
2014-10-14 14:37 10楼
回复 @ Sapphire~天翔 :
╭∩╮(︶︿︶)╭∩╮
GravatarJSX
2014-10-14 14:46 11楼
第一次写RMQ,跑了快两秒,我是渣渣
Gravatar奶猹
2014-10-30 07:47 12楼
回复 @O(∩_∩)O :
我也跑了快两秒…………
GravatarMINE·MINE
2014-10-31 08:16 13楼
写果的线段树居然过了。。。
Gravatardevil
2015-04-18 21:56 14楼
Gravatar0
2015-05-24 11:30 15楼
数组开小了三次。。。
好水的题
Gravatar一個人的雨
2015-06-14 07:44 16楼
线段树为啥2星半
Gravatar0
2015-06-14 21:07 17楼
Gravatarforever
2015-06-14 21:16 18楼

Gravatar浮生随想
2018-09-02 09:01 19楼
Gravatar牧殇
2016-02-17 15:44 20楼
GravatarSPA
2016-02-17 20:15 21楼
Max和加整反了
Gravatar森林
2016-02-17 21:26 22楼
电脑哈哈哈哈哈卡
GravatarHzoi_Go灬Fire
2016-02-18 21:13 23楼
VIP 裸ST算法...
Gravatar沉迷学习的假的Keller
2016-03-09 16:57 24楼
GravatarAntiLeaf
2017-05-25 15:52 25楼
为什么ST如此之慢?不科学...
Gravatar洛克索耶夫
2016-05-02 11:34 26楼
GravatarAntiLeaf
2017-05-25 15:52 27楼
论如何用zkw线段树卡常。。。
GravatarJobs.T
2016-05-11 15:28 28楼
线段树从来没有一次写对过
GravatarAAAAAAAAAA
2016-07-04 13:41 29楼
乱搞 分块啊分块啊才0.3s...
Gravatarsxysxy
2016-09-19 21:55 30楼
第四棵线段树依旧一遍
GravatarMealy
2016-09-05 21:04 31楼
GravatarMagic_Sheep
2016-09-19 21:21 32楼
ST写丑了,T两个点 转投线段树
GravatarJanis
2016-09-23 10:50 33楼
GravatarWeiSama
2017-03-12 10:22 34楼
为啥第一次用地址做指针
结果评测机上是T了
本地是RE了??
GravatarHeHe
2017-02-20 21:27 35楼
mdzz....满怀希望感觉能1A,结果习惯省内存,数组开小了。RERERERRERE
QAQ
GravatarkZime
2017-02-21 21:26 36楼
动态规划写不出来过来写道线段树裸题放松放松................
GravatarJustWB
2017-02-27 20:13 37楼
第一次错的太傻...
GravatarFisher.
2017-04-14 17:22 38楼
很好 原来我之前写的一直是假的RMQ
GravatarShirry
2017-04-22 08:32 39楼
干翻了卡bug的,很开心
GravatarkZime
2017-07-19 13:38 40楼
第一道动态开点 (忘删注释wa了一遍)
好爽!!!
GravatarHzoi_DK
2017-08-14 14:18 41楼
额...我的线段树果然渣,居然TLE.
Gravatarサイタマ
2017-10-15 20:43 42楼
8……848??!!
Gravatar+1s
2017-10-28 14:52 43楼

58. 延绵的山峰

★☆   输入文件:climb.in   输出文件:climb.out   简单对比
时间限制:1 s   内存限制:512 MB
题目描述
有一座延绵不断、跌宕起伏的山,最低处海拔为0,最高处海拔不超过8848米,从这座山的一端走到另一端的过程中,每走1米海拔就升高或降低1米。有Q个登山队计划在这座山的不同区段登山,当他们攀到各自区段的最高峰时,就会插上队旗。请你写一个程序找出他们插旗的高度。
 
输入文件
 
第1行,一个整数N(N<=10^6),表示山两端的跨度。
接下来N+1行,每行一个非负整数Hi,表示该位置的海拔高度,其中H0=Hn=0。
然后是一个正整数Q(Q<=7000),表示登山队的数量。
接下来Q行,每行两个数Ai, Bi,表示第i个登山队攀爬的区段[Ai,Bi],其中0<=Ai<=Bi<=N。
 
输出文件
 
Q行,每行为一个整数,表示第i个登山队插旗的高度。
 
样例输入
10
0
1
2
3
2
3
4
3
2
1
0
5
0 10
2 4
3 7
7 9
8 8
 
样例输出
4
3
4
3
2