← 返回题目列表

Codeforces · 2026/D

D. 段总和

中文机器翻译题面 查看原题

给你一个整数序列$$$[a_1, a_2, \dots, a_n]$$$。令 $$$s(l,r)$$$ 为从 $$$a_l$$$ 到 $$$a_r$$$ 的元素之和(即 $$$s(l,r) = \sum\limits_{i=l}^{r} a_i$$$)。

让我们构建另一个大小为 $$$\frac{n(n+1)}{2}$$$ 的序列 $$$b$$$,如下所示: $$$b = [s(1,1), s(1,2), \dots, s(1,n), s(2,2), s(2,3), \dots, s(2,n), s(3,3), \dots, s(n,n)]$$$。

例如,如果 $$$a = [1, 2, 5, 10]$$$,则 $$$b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10]$$$。

您收到 $$$q$$$ 查询。在第 $$$i$$$ 次查询期间,您将获得两个整数 $$$l_i$$$ 和 $$$r_i$$$,并且您必须计算 $$$\sum \limits_{j=l_i}^{r_i} b_j$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10 \le a_i \le 10$$$)。

第三行包含一个整数$$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$)。

接下来是 $$$q$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le \frac{n(n+1)}{2}$$$)。

输出

打印 $$$q$$$ 整数,其中第 $$$i$$$ 应等于 $$$\sum \limits_{j=l_i}^{r_i} b_j$$$。

示例

输入 #1

4
1 2 5 10
15
1 1
1 2
1 3
1 4
1 5
1 10
5 10
6 10
2 8
3 4
3 10
3 8
5 6
5 5
1 8

输出 #1

1
4
12
30
32
86
56
54
60
26
82
57
9
2
61