Sức mạnh dãy số


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Sức mạnh của dãy số $b_1,b_2,...,b_k$ là tổng các tích $b_i \times b_j$ với $1\le i < j\le k$.

Ví dụ: sức mạnh của dãy (2, -3, 4) được tính = $2\times (-3) + 2\times 4 + (-3)\times 4 = -10$.

Cho dãy $a_1,a_2,..., a_N$. Cho $Q$ truy vấn, hãy tính sức mạnh của dãy $a_L, a_{L+1},...,a_R$.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, Q \ (1\le N,Q\le 10^5)$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i \ (|a_i| \le 10^2)$;
  • $Q$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên $L, R \ (1\le L\le R\le N)$.

Kết quả

  • In trên $Q$ dòng, mỗi dòng chứa kết quả tương ứng cho từng truy vấn.

Chấm điểm

30; $N,Q\le 10^2$. 30; $N,Q\le 10^3$. 40; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

5 4
1 2 -1 3 7
1 4
3 5
1 2
2 3

output

5
11
2
-2

Comments

There are no comments at the moment.