Codeforces Round 815 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$a_i \le 10^9$$$.
Дан массив из $$$n$$$ целых чисел $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$. Бряп захотел найти в данном массиве самую длинную хорошую подпоследовательность.
Массив $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$, где $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$, будем называть подпоследовательностью длины $$$m$$$ массива $$$a$$$.
Подпоследовательность $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ длины $$$m$$$ называется хорошей, если выполняется следующее условие:
Здесь $$$a \oplus b$$$ обозначает побитовое исключающее ИЛИ чисел $$$a$$$ и $$$b$$$. Например, $$$2 \oplus 4 = 6$$$, а $$$3 \oplus 1=2$$$.
Так как Бряп не очень любознательная персона, он хочет знать лишь длину такой подпоследовательности. Помогите ему найти ответ на данную задачу.
Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — длина массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 10^9$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных единственное число — максимальную длину хорошей подпоследовательности.
321 255 2 4 3 1103 8 8 2 9 1 6 2 8 3
2 3 6
В первом наборе входных данных в качестве подпоследовательности мы можем выбрать оба элемента массива, так как $$$1 \oplus 1 < 2 \oplus 0$$$.
Во втором наборе входных данных мы можем взять элементы с индексами $$$1$$$, $$$2$$$ и $$$4$$$ (в $$$0$$$ нумерации). Для них выполняется: $$$2 \oplus 2 < 4 \oplus 1$$$ и $$$4 \oplus 4 < 1 \oplus 2$$$.
Название |
---|