TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1246
  • 题目
  • P1246高度平衡
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    在每天挤奶的时候,农民约翰的N头牛(1≤n≤50000)总是排成一列。有一天,约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见,他将从奶牛队列里面选一定范围内的奶牛来玩这个游戏。然而所有的牛对这个游戏都很感兴趣。农民约翰列出了Q份名单(1≤Q≤200000)和每个奶牛的高度(1≤高度≤1000000)。对于每一份名单,他想你帮助他确定在每份名单中高度最高的奶牛与高度最低的奶牛的高度差是多少。

    输入格式

    第一行为N(1≤N≤50000)和Q(1≤Q≤200000);从第2行到第N+1行,每行一个数字,表示第i头牛的高度(1≤height≤1000000);从第N+2行到第N+Q+1行,每行两个整数A和B(1≤A≤B≤N),表示从第A头牛到第B头牛的范围。

    输出格式

    从第一行到第Q行,每行一个整数,表示从第A头牛到第B头牛之间,最高牛与最矮牛的高度差。

    样例输入

    6 3
    1
    7
    3
    4
    2
    5
    1 5
    4 6
    2 2

    样例输出

    6
    3
    0


    来源  USACO 2007 January Silver