trang chủ / bài tập / powarr

Sức mạnh đoạn con

Cho mảng gồm $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ . Xét một đoạn con $a_{l}, a_{l + 1}, \dots, a_{r}$ với $1 \leq l \leq r \leq n$ . Với mỗi số nguyên dương $s$ , gọi $K_{s}$ là số lần xuất hiện của $s$ trong đoạn con đó. Sức mạnh của đoạn con được định nghĩa là tổng $K_{s} \cdot K_{s} \cdot s$ trên mọi số nguyên dương $s$ (tổng này chỉ có hữu hạn số hạng khác $0$ ).

Cho $t$ truy vấn, mỗi truy vấn gồm hai chỉ số $l, r$ . Hãy tính sức mạnh của đoạn con tương ứng với từng truy vấn.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $t$ : độ dài mảng và số truy vấn.
Dòng thứ hai chứa $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ .
$t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l, r$ ( $1 \leq l \leq r \leq n$ ): hai đầu mút của đoạn con.

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ chứa một số nguyên dương duy nhất: sức mạnh của đoạn con trong truy vấn thứ $i$ .

Ràng buộc

$1 \leq n, t \leq 2 \cdot 10^{5}$
$1 \leq a_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 2 1 2 1 1 2 1 3	3 6	Đoạn $[1, 2]$ : $K_{1} = 1, K_{2} = 1$ , sức mạnh $= 1^{2} \cdot 1 + 1^{2} \cdot 2 = 3$ . Đoạn $[1, 3]$ : $K_{1} = 2, K_{2} = 1$ , sức mạnh $= 2^{2} \cdot 1 + 1^{2} \cdot 2 = 6$ .
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20	Đoạn $[2, 7]$ : $K_{1} = 3, K_{2} = 2, K_{3} = 1$ , sức mạnh $= 3^{2} \cdot 1 + 2^{2} \cdot 2 + 1^{2} \cdot 3 = 20$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 8,00một phần

Giới hạn thời gian 3.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

C++