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
静态区间和问题
Time Limit: 250ms, Special Time Limit:500ms, Memory Limit:32768KB
Total submit users: 45, Accepted users: 42
Problem 11456 : No special judgement
Problem description
  给定N个数,序号从1到N。回答每一次的区间和询问。所谓区间和询问是指:在给定数列上,问区间[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 2
1 2 3 4 5 6 7 8 9 10
1 4
4 7
2 1
4 5
1 2
Sample Output
Case 1:
10
22
Case 2:
9
Submit   Clarifications   Judge Status  Problems  Ranklist 

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