问题 K: 简单求和（summation）

问题 K: 简单求和（summation）

时间限制: 1 Sec  内存限制: 256 MB
提交: 64  解决: 16
[提交][状态][讨论版][命题人:]

题目描述

这应该是一道简单题。
你有一个长度为 n 的序列，第 i 个元素是 ai。
定义一个区间的权值 val(L, R) 为 aL × aR。
q 次询问，每次给出一个区间 [l, r]，你需要求出来所有满足 l ≤ i ≤ j ≤ r 的 val(i, j) 的和。


输入

第一行共 2 个整数 n, q。
第二行共 n 个整数，第 i 个整数表示 ai。
接下来 q 行，每行 2 个整数表示 l, r

输出

输出共 q 行，第 i 行共 1 个整数，表示第 i 次询问的答案。


样例输入

4 4
1 2 3 4
1 2
2 3
3 4
1 3

样例输出

7
19
37
25

提示

image-20230904092118521.png

[提交][状态]