前缀拼接

题目描述

给定一个长度为 $N$ 的整数序列 $(A_1, A_2, \dots, A_N)$。

按下面的步骤构造一个长度为 $\frac{N(N+1)}{2}$ 的序列 $B$：

• 初始时 $B$ 是空序列；
• 依次对 $i = 1, 2, \dots, N$，把 $(A_1, A_2, \dots, A_i)$ 接在 $B$ 的末尾。

例如 $A = (1, 10, 100, 1000)$ 时，$B = (1, 1, 10, 1, 10, 100, 1, 10, 100, 1000)$。

给定 $Q$ 个询问，请逐个回答。

询问：给定 $L$ 和 $R$，求 $B_L + B_{L+1} + \dots + B_R$。

输入格式

第一行两个整数 $N, Q$，用一个空格隔开。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$，相邻两个整数之间用一个空格隔开。

接下来 $Q$ 行，第 $i$ 行为两个整数 $L_i, R_i$，表示第 $i$ 个询问，含义如上。相邻两个整数之间用一个空格隔开。

输出格式

输出 $Q$ 行。第 $i$ 行一个整数，表示第 $i$ 个询问的答案。

4 3
1 10 100 1000
3 6
1 10
8 8

121
1234
10

样例 1 解释

此时 $B = (1, 1, 10, 1, 10, 100, 1, 10, 100, 1000)$。

• 第 $1$ 个询问：$B_3 + B_4 + B_5 + B_6 = 10 + 1 + 10 + 100 = 121$；
• 第 $2$ 个询问：$B_1 + B_2 + \dots + B_{10} = 1 + 1 + 10 + 1 + 10 + 100 + 1 + 10 + 100 + 1000 = 1234$；
• 第 $3$ 个询问：$B_8 = 10$。

7 1
100000000 100000000 100000000 100000000 100000000 100000000 100000000
1 28

2800000000

数据范围

对于所有测试数据，保证：

• $1 \le N \le 10^5$；
• $1 \le Q \le 10^5$；
• $-10^8 \le A_i \le 10^8$；
• 对每个询问，$1 \le L_i \le R_i \le \frac{N(N+1)}{2}$；
• 所有输入值都是整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。