题目名称	182. [USACO Jan07] 均衡队形
输入输出	`lineup.in/out`
难度等级	★★☆
时间限制	4000 ms (4 s)
内存限制	128 MiB
测试数据	18
题目来源	BYVoid 于2008-10-11加入
开放分组	全部用户
提交状态
分类标签	USACO 稀疏表线段树 RMQ
	分享题解

通过：431，提交：780，通过率：55.26%
LGLJ	100	0.213 s	6.00 MiB	C++
666666666666	100	0.232 s	0.28 MiB	C++
Pine	100	0.235 s	4.52 MiB	C++
sxysxy	100	0.238 s	7.22 MiB	C++
Samle	100	0.249 s	2.68 MiB	C++
JSX	100	0.272 s	30.81 MiB	C++
yrtiop	100	0.275 s	5.99 MiB	C++
~玖湫~	100	0.284 s	44.68 MiB	C++
666666666666	100	0.299 s	0.28 MiB	C++
zhk	100	0.312 s	13.46 MiB	C++

本题关联比赛
测试

关于均衡队形的近10条评论(全部评论)
第一次登顶！！！QAQ 666666666666 2018-10-05 18:42 29楼
数组到底要开多大你才能放过我小薛也嘻哈 2017-10-29 09:15 28楼
啊，自己两段类似的代码最好也别复制粘贴... Fisher. 2017-04-19 08:15 27楼
已过 ST是个好东西虽然最后我是看网上人照着写的 +1s 2017-02-24 22:30 26楼
终于会写线段树了 HeHe 2017-02-18 12:23 25楼
无旋treap大法好 sxysxy 2016-12-06 17:21 24楼
数组开小了 AAAAAAAAAA 2016-11-15 16:45 23楼
回复 @安吶。 : %%%，听了神犇的指导，把函数名改了然后就A了。。。。(为啥啊qaq sxysxy 2016-10-17 19:10 22楼
回复 @sxysxy : 你把 maintain 这个函数改个名字。安呐一条小咸鱼。 2016-10-17 18:02 21楼
Orz,,,一发splay连T带E一脸蒙蔽...在别的oj上明明能过的... sxysxy 2016-10-17 17:55 20楼

182. [USACO Jan07] 均衡队形

★★☆ 输入文件：lineup.in 输出文件：lineup.out 简单对比
时间限制：4 s 内存限制：128 MiB

题目描述

农夫约翰的 N (1 ≤ N ≤ 50,000) 头奶牛，每天挤奶时总会按同样的顺序站好。一日，农夫约翰决定为奶牛们举行一个“终极飞盘”比赛。为简化问题，他将从奶牛队列中选出一个连续区间来进行游戏。不过，参加游戏的奶牛要玩的开心的话就不能在身高上差距太大。

农夫约翰制定了 Q (1 ≤ Q ≤ 200,000) 个预定的参赛组，给出它们的身高 (1 ≤ 身高 ≤ 1,000,000)。对每个参赛组，他需要你帮助确定组中最高牛和最低牛的身高差。

输入格式

第 1 行: 两个空格隔开的整数，N 和 Q。
第 2..N+1 行: 第 i+1 行包含一个整数表示第 i 头牛的身高。
第 N+2..N+Q+1 行: 两个整数 A 和 B(1 ≤ A ≤ B ≤ N)，表示一个从 A 到 B 的参赛组区间。

输出格式

第 1..Q 行: 每行包含一个整数来表示区间上最大身高差。

样例输入

样例输出

6
3
0