CF2026D.Sums of Segments

给定一个整数序列 $[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$ 行，每行包含两个整数 $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$ 的值。

由 ChatGPT 4.1 翻译