1136_无水之地

2022-5-16 18:17| 发布者: Hocassian| 查看: 105| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503637561700-Problem List-采集的数据-后羿采集器.html

Pro.ID

1136

Title

无水之地

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1136

AC

27

Submit

465

Ratio

5.81%

时间&空间限制

  • Time Limit: 4000/2000 MS (Java/Others)     Memory Limit: 65536/65536 K (Java/Others)
  • 描述

    在"无水之地",水资源很珍稀。这里的人常常为最大的水资源而大打出手。

    给出一个水资源的系列 a1, a2, a3, ..., an ,按顺序表示n个水资源的大小。然后是若干个查询指令,每个查询是两个整数lr,请找出lr之间最大的水资源。

    输入

    第一行是一个整数n ( 0 ≤ n ≤ 10000 ),表示水资源的数量。

    接下来一行有n个整数,对应表示 a1, a2, a3, ..., an,每个整数的范围是[1..106]。

    接下来一行是一个整数q (0 ≤ q ≤ 900000),表示查询指令的个数。

    接下来是q行,每行两个整数lr (1 ≤ lrn),表示要你求出lr之间最大的水资源。

    输出

    Description

    在"无水之地",水资源很珍稀。这里的人常常为最大的水资源而大打出手。

    给出一个水资源的系列 a1, a2, a3, ..., an ,按顺序表示n个水资源的大小。然后是若干个查询指令,每个查询是两个整数lr,请找出lr之间最大的水资源。

    Input

    第一行是一个整数n ( 0 ≤ n ≤ 10000 ),表示水资源的数量。

    接下来一行有n个整数,对应表示 a1, a2, a3, ..., an,每个整数的范围是[1..106]。

    接下来一行是一个整数q (0 ≤ q ≤ 900000),表示查询指令的个数。

    接下来是q行,每行两个整数lr (1 ≤ lrn),表示要你求出lr之间最大的水资源。

    Output

    对每个查询,输出一个整数——最大水资源的大小。

    Sample Input

    Sample #1
    1
    100
    1
    1 1


    Sample #2
    5
    1 2 3 4 5
    5
    1 2
    1 3
    2 4
    3 4
    3 5


    Sample #3
    3
    1 999999 1
    4
    1 1
    1 2
    2 3
    3 3

    Sample Output

    Sample #1
    100

    Sample #2
    2
    3
    4
    4
    5


    Sample #3
    1
    999999
    999999
    1

    Hint

    这题是RMQ模板题。

    Source

    样例输入

    Sample #1
    1
    100
    1
    1 1


    Sample #2
    5
    1 2 3 4 5
    5
    1 2
    1 3
    2 4
    3 4
    3 5


    Sample #3
    3
    1 999999 1
    4
    1 1
    1 2
    2 3
    3 3

    样例输出

    Sample #1
    100

    Sample #2
    2
    3
    4
    4
    5


    Sample #3
    1
    999999
    999999
    1

    提示

    这题是RMQ模板题。

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部