TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2045
  • 题目
  • P2045【RMQ】奶牛探洞
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    贝西计划去探索一个洞穴,洞穴中有一条很长的通道,该通道由N段构成((1 <= N <= 25,000 ,编号1..N))。每段通道有一个特定的宽度,只有腰围不超过该宽度的牛才能通过。一头牛要通过i到j这连续多段通道的话,必须满足的要求是这头牛的腰围不能超过这些通道中最窄的那条的宽度。通道的宽度都是正数,范围是1..1,000,000,000.

    贝西正在计划它的探险活动,它需要回答Q(1 <= Q <= 25,000)个这样的问题"最胖腰围是多少的牛能够通过i到j这连续若干条通道?"请帮助贝西回答这些问题。


    输入格式

    第一行,两个空格间隔的整数N和Q
    接下来N行,每行一个整数,表示对应这段通道的宽度
    接下来Q行,每行两个空格间隔的整数i和j(i<j),表示询问从第i条通道到第j条通道通过,牛最大的腰围是多少?

    输出格式

    Q行,每行一个整数表示对应问题的答案

    样例输入

    10 4
    75
    30
    100
    38
    50
    51
    52
    20
    81
    5
    1 10
    3 5
    6 9
    8 10

    样例输出

    5
    38
    20
    5


    来源  USACO OPEN2004