试题描述

长度为n的数列A，以及q个询问，每次询问一段区间的加权和s，第一个数*1，第二个数*2，以此类推。

s=ΣAi*(i-L+1) (L<=i<=R)

输入

第一行，一个整数n

第二行，n个数，表示A数组，用空格隔开。

第三行，一个正整数q

第4到第q+3行每行两个正整数L、R（L<=R），表示一段区间，用一个空格隔开。

输出

针对每个询问，输出结果。每个结果占一行。

输入示例

5

3 2 4 3 5

3

1 3

2 5

3 4

输出示例

19

39

10

其他说明

数据规模：n, q, Ai<=100000

思路见相册

1 #include 
      
        2  3 using namespace std; 4 long long a[101010],s[101010],w[101010]; 5 int main() 6 { 7     long long n,i; 8     scanf("%lld",&n); 9     for(i=1;i<=n;i++) 10     {11         scanf("%lld",&a[i]);12         s[i]=s[i-1]+a[i];13         w[i]=w[i-1]+s[i];14     }15     long long q,x,y,temp;16     scanf("%lld",&q);17     for(i=1;i<=q;i++)18     {19         scanf("%lld%lld",&x,&y);20         temp=(y-x+1)*s[y]-(w[y-1]-w[x-2]);21         printf("%lld\n",temp);22     }23     return 0;24 }