Codeforces Round 781 (Div. 2) |
---|
Закончено |
Дан массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел, пронумерованных от $$$1$$$ до $$$n$$$.
Назовём стоимостью массива $$$a$$$ величину, равную $$$\displaystyle \min_{i \neq j} a_i | a_j$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.
Есть $$$q$$$ запросов. Каждый запрос состоит из двух чисел $$$l$$$ и $$$r$$$ ($$$l < r$$$). Для каждого запроса необходимо вывести стоимость массива $$$a_{l}, a_{l + 1}, \ldots, a_{r}$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — элементы массива $$$a$$$.
Третья строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.
Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j < r_j \le n$$$) — описание $$$j$$$-го запроса.
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите $$$q$$$ чисел, где $$$j$$$-е число равно стоимости массива $$$a_{l_j}, a_{l_j + 1}, \ldots, a_{r_j}$$$.
256 1 3 2 141 22 32 42 540 2 1 107374182341 22 31 33 4
7 3 3 1 2 3 1 1073741823
В первом наборе входных данных массив $$$a$$$ выглядит так:
$$$110_2, 001_2, 011_2, 010_2, 001_2$$$.
Поэтому ответы на запросы будут следующими:
Во втором наборе входных данных массив $$$a$$$ выглядит так:
$$$00_2, 10_2, 01_2, \underbrace{11\ldots 1_2}_{30}$$$ ($$$a_4 = 2^{30} - 1$$$).
Поэтому ответы на запросы будут следующими:
Название |
---|