E. 子数组的和

传统题

2000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 。

有 $q$ 次询问，每次询问给定一个区间 $[l,r]$ 。你需要求出

$$\sum\limits_{i=l}^r \sum\limits_{j=i}^r (a_i+a_{i+1}+\ldots+a_j) $$

形式化的说：即求出子数组的所有子数组的和。

第一行输入两个数 $n$ 和 $q$ 。

接下来一行输入 $n$ 个正整数为 $a_1,a_2,\ldots,a_n$ 。

接下来 $q$ 行，每行输入两个整数 $l,r$ 。

一行 $n$ 个数，为 $1 \sim n$ 。

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 3\times 10^5$ ， $1\leq a_i\leq 100$ 。保证 $1\leq l\leq r\leq n$ 。