Xor-Subsequence (easy version)

题意翻译

### 题目描述 这是此问题的简单版本。简单版本与困难版本的唯一区别在于：在简单版本中，$a_i\leq 200$。 给你一个长为 $n$ 的整数数组 $a$，从 $0$ 开始编号。 一个长为 $m$ ，从 $0$ 开始编号的整数数组 $b$ 是数组 $a$ 的 subsequence，当且仅当 $0\leq b_0<b_1<\dots<b_{m-1}<n$。 若 $b$ 是 $a$ 的 beautiful subsequence，当且仅当满足以下条件： + $b$ 是 $a$ 的 subsequence； + $\forall p\in[0,m)\cap\textbf{N},a_{b_p}\oplus b_{p+1}<a_{b_{p+1}}\oplus b_p$。 其中 $\oplus$ 表示位运算中的异或运算。 现在，你需要求出最长的 beautiful subsequence 有多长。 ### 输入格式 第一行一个整数 $T$，表示数据组数。 对于每组数据，第一行一个整数 $n$，表示数组 $a$ 的长度。 第二行有 $n$ 个整数，表示数组 $a$。 ### 输出格式 对于每组数据，输出一行一个数，表示最长的 beautiful subsequence 的长度。 ### 数据范围 $1\leq T\leq 10^5,2\leq n\leq 3\times 10^5,0\leq a_i\leq 200,\sum n\leq 3\times 10^5$。

题目描述

It is the easy version of the problem. The only difference is that in this version $ a_i \le 200 $ . 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.

输入输出格式

输入格式

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 200 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 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 $ .

**题目大意：**

这是一个关于数组子序列的问题的简单版本。在这个版本中，数组 $ a $ 的每个元素 $ a_i $ 都满足 $ a_i \leq 200 $。

给定一个长度为 $ n $ 的整数数组 $ a $，你需要找到一个最长的“美丽”子序列。一个长度为 $ m $ 的数组 $ b $ 是数组 $ a $ 的子序列，当且仅当 $ 0 \leq b_0 < b_1 < \dots < b_{m-1} < n $。

如果子序列 $ b $ 满足以下条件，则它被称为“美丽”的：

- 对于任意 $ p $（$ 0 \leq p < m - 1 $），都满足：$ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $。

这里的 $ \oplus $ 表示位运算中的异或运算。

你需要求出最长的美丽子序列的长度。

**输入格式：**

第一行包含一个整数 $ T $，表示数据组数。

对于每组数据，第一行包含一个整数 $ n $，表示数组 $ a $ 的长度。

第二行包含 $ n $ 个整数，表示数组 $ a $ 的元素。

**输出格式：**

对于每组数据，输出一行一个数，表示最长的美丽子序列的长度。

**数据范围：**

$ 1 \leq T \leq 10^5, 2 \leq n \leq 3 \times 10^5, 0 \leq a_i \leq 200, \sum n \leq 3 \times 10^5 $。

**输入输出样例：**

**输入样例 #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
```

**说明：**

在第一个测试案例中，我们可以选择整个数组作为一个美丽的子序列，因为 $ 1 \oplus 1 < 2 \oplus 0 $。

在第二个测试案例中，我们可以选择索引为 $ 1 $, $ 2 $ 和 $ 4 $ 的元素（在 0 索引化中）。对于这些元素，满足：$ 2 \oplus 2 < 4 \oplus 1 $ 和 $ 4 \oplus 4 < 1 \oplus 2 $。**题目大意：** 这是一个关于数组子序列的问题的简单版本。在这个版本中，数组 $ a $ 的每个元素 $ a_i $ 都满足 $ a_i \leq 200 $。 给定一个长度为 $ n $ 的整数数组 $ a $，你需要找到一个最长的“美丽”子序列。一个长度为 $ m $ 的数组 $ b $ 是数组 $ a $ 的子序列，当且仅当 $ 0 \leq b_0 < b_1 < \dots < b_{m-1} < n $。 如果子序列 $ b $ 满足以下条件，则它被称为“美丽”的： - 对于任意 $ p $（$ 0 \leq p < m - 1 $），都满足：$ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $。 这里的 $ \oplus $ 表示位运算中的异或运算。 你需要求出最长的美丽子序列的长度。 **输入格式：** 第一行包含一个整数 $ T $，表示数据组数。 对于每组数据，第一行包含一个整数 $ n $，表示数组 $ a $ 的长度。 第二行包含 $ n $ 个整数，表示数组 $ a $ 的元素。 **输出格式：** 对于每组数据，输出一行一个数，表示最长的美丽子序列的长度。 **数据范围：** $ 1 \leq T \leq 10^5, 2 \leq n \leq 3 \times 10^5, 0 \leq a_i \leq 200, \sum n \leq 3 \times 10^5 $。 **输入输出样例：** **输入样例 #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 ``` **说明：** 在第一个测试案例中，我们可以选择整个数组作为一个美丽的子序列，因为 $ 1 \oplus 1 < 2 \oplus 0 $。 在第二个测试案例中，我们可以选择索引为 $ 1 $, $ 2 $ 和 $ 4 $ 的元素（在 0 索引化中）。对于这些元素，满足：$ 2 \oplus 2 < 4 \oplus 1 $ 和 $ 4 \oplus 4 < 1 \oplus 2 $。