Пёстрые ковры Баткена
В Баткене ткут полосатые ковры: ковёр — это ряд из n полос, полоса i имеет цвет c[i] (целое число). Пёстрость куска ковра с полосы l по полосу r равна сумме квадратов количеств полос каждого цвета на этом куске: Σ (cnt_v)² по всем цветам v.
Иногда ткачиха перекрашивает одну полосу. Обработайте события:
1 p x— полосаpперекрашивается в цветx;2 l r— найдите пёстрость куска сlпоr.
Входные данные
В первой строке — n и q (1 ≤ n, q ≤ 10⁵). Во второй — n чисел c[i] (1 ≤ c[i] ≤ 10⁹). В каждой из следующих q строк — событие в описанном формате (1 ≤ p ≤ n, 1 ≤ x ≤ 10⁹, 1 ≤ l ≤ r ≤ n).
Выходные данные
Для каждого события 2 выведите пёстрость в отдельной строке.
Пример 1
Вход:
5 4
1 2 1 1 3
2 1 5
1 4 2
2 1 5
2 2 4
Выход:
11
9
5
Пояснение
На куске 1…5 ковра 1 2 1 1 3 цвет 1 встречается 3 раза, цвета 2 и 3 — по разу: 9 + 1 + 1 = 11. После перекраски полосы 4 в цвет 2: 4 + 4 + 1 = 9.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, q ≤ 1000, ещё в 10 % тестов нет событий 1.
Подсказка
Алгоритм Мо с изменениями: запросы сортируются по блокам левой границы, правой границы и времени, размер блока порядка n^(2/3).
Комментарии