| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 8 | 2 | 2 | 28.571% |
В самой обычной школе в Ваканде на уроке арифметики сегодня проходят битовые операции с числами.
А именно, операции and и xor. Напомним, что битовая операция над двумя числами выполняется независимо по каждому биту. Таблицы истинности для операций and и xor выглядят следующим образом:
| $x$ | $y$ | $x$ and $y$ |
$x$ xor $y$ |
|---|---|---|---|
| $0$ | $0$ | $0$ | $0$ |
| $0$ | $1$ | $0$ | $1$ |
| $1$ | $0$ | $0$ | $1$ |
| $1$ | $1$ | $1$ | $0$ |
В начале урока учитель написал на доске последовательность длины $n$ из чисел. Затем он просит учеников последовательно выполнять следующие операции:
xor с числом $x$ ко всем элементам текущей последовательности.and с числом $x$ ко всем элементам текущей последовательности.Помогите ученикам ответить на все вопросы учителя правильно.
В первой строке содержится два целых числа $n$ и $q$ --- количество чисел в последовательности, и количество операций, которое нужно выполнить ($1 \le n \le 100\,000$, $0 \le q \le 100\,000$). В следующей строке дано $n$ целых чисел $a_i$ --- элементы исходной последовательности ($0 \le a_i < 2^{20}$). В следующих $q$ строках дано описание операций. Если строка начинается со слова <<xor>>, то это операция первого типа, дальше в той же строке дано число $x$, и ученикам нужно заменить все элементы $cur_i$ текущей последовательности на $(cur_i$ xor $x)$ ($0 \le x < 2^{20}$). Если строка начинается со слова <<and>>, то это операция второго типа, дальше в той же строке дано число $x$, и ученикам нужно заменить все элементы $cur_i$ текущей последовательности на $(cur_i$ and $x)$ ($0 \le x < 2^{20}$). Если строка начинается с символа '?', то дальше даны два целых числа $l$ и $r$, ученикам нужно посчитать количество элементов текущей последовательности $cur_i$, таких что $l \le cur_i \le r$ ($0 \le l \le r < 2^{20}$).
Для каждой операции третьего типа на новой строке выведите искомое количество чисел.
5 5 1 2 3 4 5 ? 3 4 xor 1 ? 1 2 and 2 ? 1 3
2 1 2
Пояснение к первому тесту.
После операции xor $1$, последовательность будет выглядеть следующим образом:
$0$, $3$, $2$, $5$, $4$
После операции and $2$, последовательность будет выглядеть следующим образом:
$0$, $2$, $2$, $0$, $0$