Задача №114674. Битовый хаос
-
\(upd\) \(and\) \(l\) \(r\) \(x\) — сделать \(a_i = a_i ~ \& ~ x\) (побитовая операция И) для всех \(l \le i \le r\).
-
\(upd\) \(or\) \(l\) \(r\) \(x\) — сделать \(a_i = a_i ~ | ~ x\) (побитовая операция ИЛИ) для всех \(l \le i \le r\).
-
\(upd\) \(xor\) \(l\) \(r\) \(x\) — сделать \(a_i = a_i \oplus x\) (побитовая операция XOR) для всех \(l \le i \le r\).
-
\(get\) \(and\) \(l\) \(r\) — найти побитовое И всех \(a_i\), где \(l \le i \le r\).
-
\(get\) \(or\) \(l\) \(r\) — найти побитовое ИЛИ всех \(a_i\), где \(l \le i \le r\).
-
\(get\) \(xor\) \(l\) \(r\) — найти побитовый XOR всех \(a_i\), где \(l \le i \le r\).
В первой строке вводятся два целых числа \(n, q\) \((1 \le n, q \le 500\,000)\) — размер массива \(a\) и количество запросов.
Во второй строке вводится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 10^{18})\).
В следующих \(q\) строках будет информация о запросах по одному на строке согласно условию задачи (\(1 \le l \le r \le n, 0 \le x \le 10^{18})\).
На каждый запрос типа \(get\) выведите найденный ответ. Гарантируется, что в каждом тесте есть хотя бы один такой запрос.
Тесты к этой задаче состоят из девяти групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 11 | \(n \leq 1000\) | \(q \le 1000\) | 0 | |
| 2 | 11 | – | – | Применяются только операции \(upd\) \(xor\) и \(get\) \(xor\) | |
| 3 | 13 | – | – | Нет запросов изменения | |
| 4 | 12 | – | – | Применяются только операции \(upd\) \(and\) и \(get\) \(xor\) | |
| 5 | 12 | – | \(q \leq 50\,000\) | 0 | Значения в массиве и в запросах изменения не превосходят \(10^9\). |
| 6 | 13 | – | – | Применяются только операции \(upd\) \(xor\) и \(get\) \(and\) | |
| 7 | 12 | – | – | Применяются операции, связанные с \(and\) и \(or\) | |
| 8 | 12 | \(n \leq 300\,000\) | \(q \le 300\,000\) | 0, 1 | |
| 9 | 4 | – | – | 0 – 8 | |
10 10 5 7 3 10 12 0 11 15 14 31 get or 3 7 get xor 2 9 upd and 1 5 14 upd xor 3 10 7 get xor 1 10 get and 9 10 upd or 3 8 6 get xor 1 10 get or 5 5 get xor 4 6
15 8 19 8 19 15 7