3189. 求和

单点时限: 3.0 sec

内存限制: 256 MB

有一个数组,由$n(1≤n≤1000)$个值小于等于100的正整数元素组成。用该数组的每个非空子数组(显然共有n*(n+1)/2个子数组)的元素之和建立一个新的数组。对新数组按递增次序排序。

例如:数组[2, 3, 2]的子数组有6个:[2], [3], [2], [2, 3], [3, 2], [2, 3, 2]。排序后新数组为[2, 2, 3, 5, 5, 7]。

注意:子数组指连续的元素组成的数组。

现在给定L,U表示新数组的下标(这里假设数组的下标从1开始计),$1≤L≤U≤n*(n+1)/2$,计算出下标L到U的元素的和。

L,U共有$m(1≤m≤20)$组。

例如: 前面例子中L=1,U=2时的和为4,L=2,U=4时的和为10。

输入格式

第 $1$ 行:整数 $T$ ($1 \le T \le 10$) 为问题数。

第$2~m+3$行:第一个问题的数据。一行由一个空格分隔的两个整数,表示n和m。下一行是原数组的n个由一个空格分隔的元素。后面是m行L和U, L和U之间有一个空格。

第$m+3~T*(m+2)+1$行:后面问题的数据,格式与第一个问题相同。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等),然后是m行,在每一行中输出按要求计算出的和。

样例

Input
3
1 1
1
1 1
3 2
2 3 2
1 2
2 4
5 5
5 4 3 2 1
1 1
1 10
1 15
3 8
4 11
Output
case #0:
1
case #1:
4
10
case #2:
1
45
105
26
48

226 人解决,275 人已尝试。

376 份提交通过,共有 1110 份提交。

2.5 EMB 奖励。

创建: 3 年,6 月前.

修改: 2 年,1 月前.

最后提交: 6 天,5 小时前.

来源: N/A