该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
区间加权和
题目描述
输入一个长度为 n 的整数序列 a,下标从 1 开始。
接下来再输入 m 个询问,每个询问输入一对 l,r。
记每次询问的连续子序列 [al,al+1,...,ar] 为序列 A: [A1,A2,...,Ar−l+1].
对于每个询问,求 ∑i=1∣A∣(Ai∗i) 的值。
输入描述
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。
输出描述
共 m 行,每行输出一个询问的结果。
样例输入
5 3
2 1 3 6 4
1 2
1 3
2 4
样例输出
4
13
25
样例解释
对于第一组询问,结果为 2∗1+1∗2=4;
对于第二组询问,结果为 2∗1+1∗2+3∗3=13;
对于第三组询问,结果为 1∗1+3∗2+6∗3=25。
数据范围与约定
对于 50% 的数据,1≤n,m≤5000;
对于 100% 的数据,1≤n,m≤105,1≤l≤r≤n,序列中的每个值 x 满足 x∈[−106,106].