Pro.ID1136 Title无水之地 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1136 AC27 Submit465 Ratio5.81% 时间&空间限制描述在"无水之地",水资源很珍稀。这里的人常常为最大的水资源而大打出手。 给出一个水资源的系列 a1, a2, a3, ..., an ,按顺序表示n个水资源的大小。然后是若干个查询指令,每个查询是两个整数l和r,请找出l和r之间最大的水资源。 输入第一行是一个整数n ( 0 ≤ n ≤ 10000 ),表示水资源的数量。 接下来一行有n个整数,对应表示 a1, a2, a3, ..., an,每个整数的范围是[1..106]。 接下来一行是一个整数q (0 ≤ q ≤ 900000),表示查询指令的个数。 接下来是q行,每行两个整数l和r (1 ≤ l ≤ r ≤ n),表示要你求出l和r之间最大的水资源。 输出Description 在"无水之地",水资源很珍稀。这里的人常常为最大的水资源而大打出手。 给出一个水资源的系列 a1, a2, a3, ..., an ,按顺序表示n个水资源的大小。然后是若干个查询指令,每个查询是两个整数l和r,请找出l和r之间最大的水资源。 Input 第一行是一个整数n ( 0 ≤ n ≤ 10000 ),表示水资源的数量。 接下来一行有n个整数,对应表示 a1, a2, a3, ..., an,每个整数的范围是[1..106]。 接下来一行是一个整数q (0 ≤ q ≤ 900000),表示查询指令的个数。 接下来是q行,每行两个整数l和r (1 ≤ l ≤ r ≤ n),表示要你求出l和r之间最大的水资源。 Output 对每个查询,输出一个整数——最大水资源的大小。 Sample Input Sample #1 Sample Output Sample #1 Hint 这题是RMQ模板题。 Source 样例输入Sample #1 样例输出Sample #1 提示这题是RMQ模板题。 作者 |