放传送门：Spasmodic (AT Lv.16) 。
哈哈！你被骗了……才怪！
思路
我们可以按照 LIS 的思路，得出一个朴素的 DP 法（$ O(n^2) $）：
\[f_i = \max_{0 \leq j < i, a_j \oplus i < a_i \oplus j} f_j + 1 \]考虑优化 $ a_j \oplus i < a_i \oplus j $ 。
首先，我们需要引入一条：$ \max \{ x - y, y - x \} \leq x \oplus y \leq x + y $ 。
则 $ i - a_j < a_i + j $ （最保守情况）。
解不等式，$ i - j < a_i + a_j \leq 200 + 200 = 400 $ ，所以只需要枚举最后的 $ 400 $ 个即可。
代码
#include <bits/stdc++.h>
using namespace std;
int a[300005];
int f[300005];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
f[i] = 1;
for (int j = max(0, i - 400); j < i; j++) {
if ((a[j] ^ i) < (a[i] ^ j)) {
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
printf("%d\n", ans);
}
return 0;
}