A15319. Xor-Subsequence (hard version)
编程题
普及/提高-
知识点
题目描述
It is the hard version of the problem. The only difference is that in this version $a_i \le 10^9$ .
You are given an array of $n$ integers $a_0, a_1, a_2, \ldots a_{n - 1}$ . Bryap wants to find the longest beautiful subsequence in the array.
An array $b = [b_0, b_1, \ldots, b_{m-1}]$ , where $0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$ , is a subsequence of length $m$ of the array $a$ .
Subsequence $b = [b_0, b_1, \ldots, b_{m-1}]$ of length $m$ is called beautiful, if the following condition holds:
- For any $p$ ( $0 \le p < m - 1$ ) holds: $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$ .
Here $a \oplus b$ denotes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of $a$ and $b$ . For example, $2 \oplus 4 = 6$ and $3 \oplus 1=2$ .
Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.
这是问题的困难版本。唯一不同的是，在这个版本中 $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$ 是数组 $a$ 中长度为 $m$ 的子序列。
如果以下条件成立，则长度为 $m$ 的子序列 $b = [b_0, b_1, \ldots, b_{m-1}]$ 称为优美序列：
- 对于任意 $p$ ( $0 \le p < m - 1$ ) 都成立： $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$ .
这里的 $a \oplus b$ 表示 $a$ 和 $b$ 的 [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。例如， $2 \oplus 4 = 6$ 和 $3 \oplus 1=2$ 。
Bryap 是个简单的人，所以他只想知道最长的子序列的长度。请帮助 Bryap 找到问题的答案。
You are given an array of $n$ integers $a_0, a_1, a_2, \ldots a_{n - 1}$ . Bryap wants to find the longest beautiful subsequence in the array.
An array $b = [b_0, b_1, \ldots, b_{m-1}]$ , where $0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$ , is a subsequence of length $m$ of the array $a$ .
Subsequence $b = [b_0, b_1, \ldots, b_{m-1}]$ of length $m$ is called beautiful, if the following condition holds:
- For any $p$ ( $0 \le p < m - 1$ ) holds: $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$ .
Here $a \oplus b$ denotes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of $a$ and $b$ . For example, $2 \oplus 4 = 6$ and $3 \oplus 1=2$ .
Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.
这是问题的困难版本。唯一不同的是，在这个版本中 $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$ 是数组 $a$ 中长度为 $m$ 的子序列。
如果以下条件成立，则长度为 $m$ 的子序列 $b = [b_0, b_1, \ldots, b_{m-1}]$ 称为优美序列：
- 对于任意 $p$ ( $0 \le p < m - 1$ ) 都成立： $a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$ .
这里的 $a \oplus b$ 表示 $a$ 和 $b$ 的 [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。例如， $2 \oplus 4 = 6$ 和 $3 \oplus 1=2$ 。
Bryap 是个简单的人，所以他只想知道最长的子序列的长度。请帮助 Bryap 找到问题的答案。
输入格式
The first line contains a single integer $t$ ( $1 \leq t \leq 10^5$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ( $2 \leq n \leq 3 \cdot 10^5$ ) — the length of the array.
The second line of each test case contains $n$ integers $a_0,a_1,...,a_{n-1}$ ( $0 \leq a_i \leq 10^9$ ) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .
输入
第一行包含一个整数 $t$ ( $1 \leq t \leq 10^5$ )--测试用例数。测试用例说明如下。
每个测试用例的第一行包含一个整数 $n$ ( $2 \leq n \leq 3 \cdot 10^5$ )( $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$ 。
The first line of each test case contains a single integer $n$ ( $2 \leq n \leq 3 \cdot 10^5$ ) — the length of the array.
The second line of each test case contains $n$ integers $a_0,a_1,...,a_{n-1}$ ( $0 \leq a_i \leq 10^9$ ) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .
输入
第一行包含一个整数 $t$ ( $1 \leq t \leq 10^5$ )--测试用例数。测试用例说明如下。
每个测试用例的第一行包含一个整数 $n$ ( $2 \leq n \leq 3 \cdot 10^5$ )( $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$ 。
输出格式
For each test case print a single integer — the length of the longest beautiful subsequence.
输出
为每个测试用例打印一个整数--最长优美子序列的长度。
输出
为每个测试用例打印一个整数--最长优美子序列的长度。
输入输出样例
输入 #1
3 2 1 2 5 5 2 4 3 1 10 3 8 8 2 9 1 6 2 8 3
输出 #1
2 3 6
说明/提示
In the first test case, we can pick the whole array as a beautiful subsequence because $1 \oplus 1 < 2 \oplus 0$ .
In the second test case, we can pick elements with indexes $1$ , $2$ and $4$ (in $0$ indexation). For this elements holds: $2 \oplus 2 < 4 \oplus 1$ and $4 \oplus 4 < 1 \oplus 2$ .
备注
在第一个测试案例中，我们可以选择整个数组作为优美的子序列，因为 $1 \oplus 1 \lt; 2 \oplus 0$ .
在第二个测试用例中，我们可以选取索引为 $1$ 、 $2$ 和 $4$ （在 $0$ 索引中）的元素。对于这些元素，我们可以 $2 \oplus 2 \lt; 4 \oplus 1$ 和 $4 \oplus 4 \lt; 1 \oplus 2$ 。
In the second test case, we can pick elements with indexes $1$ , $2$ and $4$ (in $0$ indexation). For this elements holds: $2 \oplus 2 < 4 \oplus 1$ and $4 \oplus 4 < 1 \oplus 2$ .
备注
在第一个测试案例中，我们可以选择整个数组作为优美的子序列，因为 $1 \oplus 1 \lt; 2 \oplus 0$ .
在第二个测试用例中，我们可以选取索引为 $1$ 、 $2$ 和 $4$ （在 $0$ 索引中）的元素。对于这些元素，我们可以 $2 \oplus 2 \lt; 4 \oplus 1$ 和 $4 \oplus 4 \lt; 1 \oplus 2$ 。