Задача №114776. Испытание силомера
Сайтама выполняет последовательные удары по силомеру. Силомер представляет из себя массив целых чисел длины \(n\). Изначально \(i\)-е число массива равно \(a_i\) для всех \(i\).
Вам необходимо обработать \(q\) событий, происходящих с силомером. Событие номер \(i\) может быть одного из трех типов:
- подходит наблюдатель и просит посчитать сумму чисел массива на отрезке \([l_i; r_i]\), то есть величину \(a_{l_i} + a_{{l_i}+1} + \ldots + a_{r_i}\);
- Сайтама наносит обычный удар силы \(x_i\) по отрезку \([l_i; r_i]\): всем элементам массива на позициях от \(l_i\) до \(r_i\) включительно присваивается значение \(x_i\)
- Сайтама наносит сильный удар по отрезку \([l_i; r_i]\): для всех \(j\) от \(l_i\) до \(r_i\) включительно происходит присваивание \(a_j \gets \mathtt{popcount}(a_j)\).
Здесь \(\mathtt{popcount}(x)\) — это количество единичных бит в двоичной записи числа \(x\). Иными словами, при событии третьего типа каждое число на отрезке события заменяется на количество своих единичных бит.
На каждый подход наблюдателя, то есть событие первого типа, сообщите ему интересующую его сумму.
В первой строке записаны два целых числа \(n\) и \(q\) — длина массива и количество событий (\(1 \leqslant n, q \leq 2 \cdot 10^5\)).
Во второй строке через пробел записаны \(n\) целых чисел \(a_1\), ..., \(a_n\) — изначальные элементы массива силомера (\(0 \leqslant a_i \leqslant 10^9\)).
Следующие \(q\) строк описывают события. Первое число \(t_i\) в описании события — тип события (\(1 \leqslant t \leqslant 3\)). Следующие два заданные через пробел числа — это границы отрезка \(l_i\) и \(r_i\) (\(1 \leqslant l_i \leqslant r_i \leqslant n\)). Если это событие второго типа, то есть \(t_i = 2\), далее следует число \(x_i\), обозначающее, что надо выполнить присваивания \(a_j \gets x_i\) для всех \(l_i \leqslant j \leqslant r_i\) (\(0 \leqslant x_i \leqslant 10^9\)).
Для каждого события первого типа выведите в отдельной строке сумму элементов массива на отрезке, заданном этим событием.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 12 | \(n, q \leqslant 5000\) | – | полная |
| 2 | 7 | все \(a_i\) и \(x_i\) — степени двойки | – | полная |
| 3 | 4 | все \(a_i\) и \(x_i\) — степени двойки или нули | 2 | полная |
| 4 | 9 | \(t_i \neq 2\) для всех \(i\) | – | полная |
| 5 | 5 | для всех событий второго типа \(l_i = r_i\) | 4 | полная |
| 6 | 12 | \(a_i, x_i \leqslant 20\) | – | полная |
| 7 | 15 | \(n \leqslant 10^5\) и \(q \leqslant 10^4\) | 1 | полная |
| 8 | 16 | все события первого типа следуют строго позже событий второго и третьего типов | – | полная |
| 9 | 20 | нет | 1 – 8 | первая ошибка |
6 6 9 1 3 1 6 3 2 2 3 9 2 4 5 10 3 2 4 1 2 4 1 2 6 3 2 5
6 19
5 6 0 3 4 1 1 1 2 5 2 2 3 8 3 1 4 3 2 2 1 3 4 2 3 5 5
9 2