Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче.
Однажды Саше попалась последовательность $$$a$$$, состоящая из $$$10^9$$$ целых неотрицательных чисел. Ему известны значения первых $$$n$$$ элементов последовательности, остальные элементы равны нулю. Саша любит битовые операции и структуры данных, поэтому он решил дать Вам следующую задачу: необходимо выполнить $$$q$$$ запросов. Запросы бывают двух типов:
1 $$$i$$$ $$$v$$$ — заменить элемент с индексом $$$i$$$ на число $$$v$$$, т.е. присвоить $$$a_{i}$$$ = $$$v$$$.
2 $$$z$$$ — вычислить количество целых неотрицательных чисел $$$x$$$, таких что $$$(a_{1}$$$ $$$or$$$ $$$a_{2}$$$ $$$or$$$ ... $$$or$$$ $$$a_{10^9}$$$ $$$or$$$ $$$x) \leq z$$$
Напишите программу, которая сможет обработать эти запросы достаточно быстро.
В первой строке входных данных содержится одно целое число $$$n$$$ (1 $$$\leq$$$ $$$n$$$ $$$\leq$$$ $$$100$$$ $$$000$$$) — количество первых элементов массива $$$a$$$, которые знает Саша.
Во второй строке содержится $$$n$$$ целых чисел $$$a_1$$$, $$$a_{2}$$$, ... $$$a_{n}$$$ ($$$0$$$ $$$\leq$$$ $$$a_{i}$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
В третьей строке входных данных содержится одно целое число $$$q$$$ ($$$1$$$ $$$\leq$$$ $$$q$$$ $$$\leq$$$ $$$100$$$ $$$000$$$) — количество запросов.
Следующие $$$q$$$ строк описывают запросы. В каждой из них находится числo $$$t$$$ ($$$1$$$ $$$\leq$$$ $$$t$$$ $$$\leq$$$ $$$2$$$) — тип запроса.
Если $$$t$$$ = 1, то в строке содержатся еще два целых числа $$$i$$$ и $$$v$$$ ($$$1$$$ $$$\leq$$$ $$$i$$$ $$$\leq$$$ $$$10^9$$$, $$$0$$$ $$$\leq$$$ $$$v$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
Если $$$t$$$ = 2, то в строке содержится еще одно целое число $$$z$$$ ($$$0$$$ $$$\leq$$$ $$$z$$$ $$$\leq$$$ $$$2^{30} - 1$$$).
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице. Исключение составляют группы $$$1$$$ и $$$2$$$, которые оцениваются за каждый пройденный тест отдельно.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия |
| 1 | 10 | $$$n$$$, $$$q$$$ = $$$1$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, все запросы второго типа | – | Потестовая оценка |
| 2 | 20 | $$$n$$$, $$$q$$$ $$$\leq$$$ $$$500$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, во всех запросах первого типа $$$i$$$ $$$\leq$$$ $$$n$$$ | – | Потестовая оценка |
| 3 | 20 | $$$n$$$ $$$\leq$$$ $$$7000$$$ и $$$a_{i}$$$, $$$z$$$, $$$v$$$ $$$\leq$$$ $$$2^{10} - 1$$$, во всех запросах первого типа $$$i \le n$$$ | 0, 1, 2 | – |
| 4 | 20 | $$$n$$$ $$$\leq$$$ $$$7000$$$, $$$q$$$ $$$\leq$$$ $$$500$$$ | 0, 1, 2 | – |
| 5 | 30 | – | 0, 1, 2, 3, 4 | – |
34 2 421 1 12 8
8
62 0 2 5 7 452 132 02 112 282 29
8 0 8 24 24
Операция $$$or$$$ обозначает операцию побитового «ИЛИ».
Побитовое «ИЛИ» — бинарная операция, действие которой эквивалентно применению логического «ИЛИ» к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0, иначе двоичный разряд результата равен 1.
Разберем первый пример из условия. Изначально дана последовательность $$$[4, 2, 4]$$$, после первого запроса $$$a_1=1$$$ последовательность становится $$$[1, 2, 4]$$$. Поступает второй запрос $$$z=8$$$. Можно убедиться, что для всех $$$x$$$ от $$$0$$$ до $$$7$$$ выполняется $$$(1$$$ $$$or$$$ $$$2$$$ $$$or$$$ $$$4$$$ $$$or$$$ $$$x) \le 8$$$, а для всех $$$x \gt 7$$$ выполняется $$$(1$$$ $$$or$$$ $$$2$$$ $$$or$$$ $$$4$$$ $$$or$$$ $$$x) \gt 8$$$. Поэтому ответ на второй запрос равен $$$8$$$.
| Name |
|---|