单点时限: 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\sim m+3$ 行:第一个问题的数据。一行由一个空格分隔的两个整数,表示 $n$ 和 $m$。下一行是原数组的 $n$ 个由一个空格分隔的元素。后面是 $m$ 行 $L$ 和 $U$,$L$ 和 $U$ 之间有一个空格。
第 $m+3\sim T\times (m+2)+1$ 行:后面问题的数据,格式与第一个问题相同。
对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0:
等),然后是 $m$ 行,在每一行中输出按要求计算出的和。
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
case #0: 1 case #1: 4 10 case #2: 1 45 105 26 48