Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + … + (y – x + 1) * A[y].
Date de intrare
Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fiecare linie se află două numere naturale separate printr-un spațiu reprezentând x și y.
Date de ieșire
Fișierul de ieșire qtsume.out va conține pe Q linii, pe linia i aflându-se răspunsul la a i-a întrebare în ordinea citirii.
Restricții și precizări
1 ≤ N, Q ≤ 100.000
1 ≤ A[i] ≤ 1.000.000
1 ≤ x ≤ y ≤ N
Exemplu
qtsume.in
5
3 1 2 3 5
3
1 2
1 5
2 4
qtsume.out
5
48
14
Explicație
Pentru a 3-a întrebare avem A[2] + 2 * A[3] + 3 * A[4] = 1 + 2 * 2 + 3 * 3 = 14
Solutie
#include <fstream>
#include <iostream>
using namespace std;
long long int a[100005],s[100005],t[100005];
int main()
{
ifstream cin("qtsume.in");
ofstream cout("qtsume.out");
long long int n,q,x,y;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
t[i]=t[i-1]+i*a[i];
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>x>>y;
cout<<t[y]-t[x-1]-(x-1)*(s[y]-s[x-1])<<'\n';
}
return 0;
}