| Яндекс.Алгоритм 2011: Раунд 2 |
|---|
| Закончено |
Имеется массив натуральных чисел a1, a2, ..., an. Рассмотрим некоторый его подмассив al, al + 1, ..., ar, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через Ks число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений Ks·Ks·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.
Необходимо вычислить мощности каждого из t заданных подмассивов.
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ ai ≤ 106) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
3 2
1 2 1
1 2
1 3
3
6
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
20
20
20
Рассмотрим следующий массив (см. пример 2) и его подмассив [2, 7] (цветом выделены элементы подмассива):
