Задача №115182. Опять запросы
Дан массив \(a_0,\ a_1,\ \ldots,\ a_{2^n-1}\) размера \(2^n\). Обратите внимание, что элементы нумеруются с нуля.
Поступает \(q\) запросов двух видов:
- \(1\) \(l\) \(r\) \(k\) \(v\). В этом случае нужно элементы \(a_{l \oplus k}\), \(a_{(l+1)\oplus k}\), \(\ldots\), \(a_{r \oplus k}\) заменить на \(v\).
- \(2\) \(l\) \(r\) \(k\). В этом случае нужно посчитать сумму \(a_{l \oplus k} + a_{(l + 1) \oplus k} + \dots + a_{r \oplus k}\).
Напомним, что символом «\(\oplus\)» обозначается операция побитового исключащего ИЛИ (XOR).
Первая строка содержит единственное целое число \(n\) \((0 \le n \le 20)\).
Вторая строка содержит \(2^n\) целых чисел \(a_0,\ a_1,\ \ldots,\ a_{2^n-1}\) (\(0 \le a_i \le 10^7\)) — элементы массива.
Третья строка содержит единственное целое число \(q\) \((1 \le q \le 10^6)\) — количество запросов.
Следующие \(q\) строк содержат описание запросов. В \(i\)-й из них находится целое число \(t_i\) (\(1 \le t_i \le 2\)).
- Если \(t_i = 1\), то далее строка содержит четыре целых числа \(l_i\), \(r_i\), \(k_i\) и \(v_i\) (\(0 \le l_i \le r_i < 2^n\), \(0 \le k_i < 2^n\), \(0 \le v_i \le 10^9\)). В этом случае нужно каждому из элементов \(a_{l_i \oplus k_i}\), \(a_{(l_i+1)\oplus k_i}\), \(\ldots\), \(a_{r_i \oplus k_i}\) присвоить \(v_i\).
- Если \(t_i = 2\), то далее строка содержит три целых числа \(l_i\), \(r_i\) и \(k_i\) (\(0 \le l_i \le r_i < 2^n\), \(0 \le k_i < 2^n\)). В этом случае нужно посчитать значение выражения \(a_{l_i \oplus k_i} + a_{(l_i + 1) \oplus k_i} + \ldots + a_{r_i \oplus k_i}\).
Для каждого запроса второго типа выведите искомую сумму.
В первом запросе \(a_{4 \oplus 1} + a_{5 \oplus 1} + a_{6 \oplus 1} + a_{7 \oplus 1} = a_5 + a_4 + a_7 + a_6 = 22\)
Во втором запросе нужно заменить элементы \(a_{1 \oplus 3}, a_{2 \oplus 3}, a_{3 \oplus 3}, a_{4 \oplus 3}\) и \(a_{5 \oplus 3} \) на \(8\). Массив после этих изменений будет равен \(8, 8, 8, 4, 3, 7, 8, 8\).
В последнем запросе \(a_{4 \oplus 1} + a_{5 \oplus 1} + a_{6 \oplus 1} + a_{7 \oplus 1} = 26\).
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n\) | \(q\) | \(a_i\) | \(v_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 19 | \(n \le 10\) | \(q \le 1000\) | – | – | \(0\) | |
| 2 | 17 | \(n \le 17\) | \(q \le 200\,000\) | – | – | – | \(k_i\) степень двойки. Если \(t_i = 1\), то \(l_i = r_i\) |
| 3 | 11 | – | – | \(a_i \le 1\) | – | – | \(t_i = 2\) |
| 4 | 13 | – | – | \(a_i \le 1\) | \(v_i \le 1\) | \(3\) | |
| 5 | 12 | \(n \le 17\) | \(q \le 200\,000\) | – | – | – | \(t_i = 2\) |
| 6 | 9 | \(n \le 17\) | \(q \le 200\,000\) | – | – | 2 | Если \(t_i = 1\), то \(l_i = r_i\) |
| 7 | 10 | \(n \le 17\) | \(q \le 200\,000\) | – | – | \(0\), \(1\), \(2\), \(5\), \(6\) | |
| 8 | 9 | – | – | – | – | \(0\) – \(7\) | Offline-проверка. |
3 1 5 8 4 3 7 8 4 3 2 4 7 1 1 1 5 3 8 2 4 7 1
22 26