Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
静态RMQ问题
Time Limit: 250ms, Special Time Limit:500ms, Memory Limit:32768KB
Total submit users: 52, Accepted users: 48
Problem 11455 : No special judgement
Problem description
  给定N个数,序号从1到N。回答每一次的RMQ询问。所谓RMQ询问是指:在给定数列上,问区间[s,e]之间的极值是多少,本题所问的是极大值。
输入范围为1≤s≤e≤N≤100000。

Input
  输入有多个案例。每个案例的第一行是2个数N和M(M的取值范围同N)。其后一行是N个数。接下来有M行,每行2个数,代表这一次RMQ查询的s和e。题目保证所有出现的数都在32位整型范围之内。

Output
  对每一个案例,首先输出一行,如样例所示,注意冒号后面没有空格。然后对每一次RMQ询问,输出一行为其答案。

Sample Input
10 3
1 2 3 4 5 6 7 8 9 10
1 4
4 7
2 8
2 1
4 5
1 2
Sample Output
Case 1:
4
7
8
Case 2:
5
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2011 today,12073060 total, since 2010-05-07