Пёстрые ковры Баткена


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 4.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В Баткене ткут полосатые ковры: ковёр — это ряд из 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).


Комментарии

Еще нет ни одного комментария.