前言
这道题的弱化版 CF1720D1 出现在模拟赛上，大家都用了弱化版的思路即向前扫描256个元素暴力计算 DP。如果想具体了解的就去看看弱化版的题解吧。
但弱化版的思路（除 DP 外）在此题几乎毫无落脚之地，甚至毫无关系。我在考场上曾对 $ 0 \leq a_i \leq 10^2 $ 感到了疑惑——甚至都没想到前面的思路，而是经过一些思考（尝试了很多错误思路）后想到了 Trie 树。
提供一些错误的思路：
1，不等式变形后的二维偏序：
由要求：
$ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $
不等式左右各异或上 $ b_{p} \oplus b_{p+1} $ 得：
$ a_{b_p} \oplus b_{p} < a_{b_{p + 1}} \oplus b_{p + 1} $
再将 $ a_{b_p} \oplus b_{p} $ 整体作为这个元素的值，进行最长上升子序列的求长度，即为最终答案。
2，不等式变形后的排序后的二维偏序：
由要求：
$ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $
猜测这种比较方式满足传递性：
即：
若有：
$ a_{b_{p-1}} \oplus b_{p} < a_{b_{p}} \oplus b_{p-1} $
$ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $
则有：
$ a_{b_{p-1}} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_{p-1} $
将原序列进行排序，然后以排序后随之变换的下标作为元素的进行最长上升子序列的求长度，即为最终答案。
但很遗憾，上述的做法都是错误的！
首先据我所知，异或几乎不能运用于不等式的计算，它不满足几乎其它所有运算符号的不等式运算性质，大家可以尝试一些具体的数进行验证。
省流：思路1中的变形是完全错误的。
其次，同样因为异或不满足几乎其它所有运算符号的不等式运算性质，思路2中的传递性实际也是不满足的。
省流：思路2中的排序是完全错误的。
但是这些错误思路也提供给我们另一个思路，如果我们将思路1具体写出来，并且尝试列出了 DP 式子，那么我们就可以知道大概要用某种数据结构来在可接受的时间内求出 DP 的值。
如果没有想到 DP 方程的就去看看其他同学的弱化版题解吧，这里不会多说。
正题
首先回收上文，我们猜想要用一种数据结构来维护无特殊限制数据向前以特殊方式比较的可选集合。但是由前面的错误思路我们也可以明白单纯地移项，用树状数组之类的直接映射式数据结构肯定是无法直接维护的。然而本题异或的计算方式和相互交错进行计算比较的特殊性也提醒我们——有一种数据结构完全满足上述的要求，即 Trie 树。
基础的 Trie 树一般维护字符串的查询，复杂度一般为 \(O(length)\)，其中 \(length\) 为字符串的长度。这里不再多说，没有基础的同学可以先去做做 Trie 树的基础题。
然而许多同学在想到 Trie 树后依然卡壳而没有深入思考，因为不知道用怎样的形式存储和询问，所以放弃了思考。但是实际上此题的难点也正在于此，我们发现存储的并不应是“一个值”，而是“两个值”，而询问时的比较也应该由“两个值”对“两个值”进行交错比较。
于是我们就有了一个基本的思路，即从前往后遍历，对每个位置先询问后存储，存储时由元素对的二进制高位到低位依次存储，因为是元素对进行比较，所以存储时按照 \((a_i, i)\) 的 类似（元素，下标）作为键值对，DP 的值作为存储值的方式存储，而询问时按照 \((i, a_i)\) 的类似（下标，元素）的方式询问，求是否有已存在于 Trie 树中的元素对 \((a_j, j)\) 对询问元素对 \((i, a_i)\) 满足：
\(a_j \oplus i < a_i \oplus j\)
并求出满足上述条件的 \(j\) 中最大的 \(f_j\)。
Q:
为什么要在存储和询问中分别用 \((a_i, i)\) 和 \((i, a_i)\) 的形式？
A:
因为我们发现题目的比较方式是交错进行比较，所以为了简化问题，就颠倒过来询问，这样两个元素对 \((a, b)\) 和 \((c, d)\) 就可以直接比较 \(a \oplus c\) 与 \(b \oplus d\) 的值而不用分类进行“这个元素对是存储在 Trie 树中的键值对还是正在询问的键值对？”的判断，成功简化了问题。
Q:
这样的 Trie 树怎样设置存储和询问，时间复杂度怎样呢？
A:
这里我们正式引出本题我认为的最难点，首先存储时并不能像普通的 Trie 树那样存储从二进制高位到低位的“0/1”式的分支存储，而应该是对于元素对的两个值在当前位上的不同情况分有“00/01/10/11”四种情况：
设元素对为 \((a, b)\)，当前考虑二进制下从低到高的第 \(e\) 位。
00：\(a\) 的第 \(e\) 位为0，\(b\) 的第 \(e\) 位为0。
01：\(a\) 的第 \(e\) 位为0，\(b\) 的第 \(e\) 位为1。
10：\(a\) 的第 \(e\) 位为1，\(b\) 的第 \(e\) 位为0。
11：\(a\) 的第 \(e\) 位为1，\(b\) 的第 \(e\) 位为1。
进行这样的情况分类并进入相应的下一层，再对二进制下从低到高的第 \(e - 1\) 位进行同样的操作。
同时在每个 Trie 结构体 \(tr_p\) 中记录 \(maxf_{(0,0)}\)，\(maxf_{(0,1)}\)，\(maxf_{(1,0)}\)，\(maxf_{(1,1)}\)，表示按照上述情况的分类下，所有满足有包括当前位的二进制高位前缀的元素对中，最大的 \(f\) 的值，在存储时顺便更新即可。
这时的查询也要分情况讨论，种类跟上述一样，但处理方式要特别说明一下：
设询问的元素对为 \((a,b)\)，Trie 树内部存储的元素对为 \((c, d)\)，对于一个数 \(x\) 记其二进制下第 \(e\) 位为 \(x(e)\)。
询问的元素对在第 \(e\) 位的种类为00即 \(a(e) = 0\)，\(b(e) = 0\) 时：
1，通过异或让这一位上的数相等，所以对应的 \((c, d)\) 应该有 \(a(e) \oplus c(e) = b(e) \oplus d(e)\)，所以分类讨论下一次递归询问分别有 \(c(e) = 0, d(e) = 0\) 和 \(c(e) = 1, d(e) = 1\) 两种情况，分别递归求值。
2，通过异或让这一位上的数直接满足 \(a \oplus c < b \oplus d\)，我们钦定这个询问函数在执行第 \(e\) 位时比其高的位上的数都相等，所以应该满足 \(a(e) \oplus c(e) < b(e) \oplus d(e)\)，所以讨论取值有 \(c(e) = 0, d(e) = 1\)，通过 \(maxf_{(0,1)}\) 直接求值。
询问的元素对在第 \(e\) 位的种类为01即 \(a(e) = 0\)，\(b(e) = 1\) 时：
1，通过异或让这一位上的数相等，所以对应的 \((c, d)\) 应该有 \(a(e) \oplus c(e) = b(e) \oplus d(e)\)，所以分类讨论下一次递归询问分别有 \(c(e) = 1, d(e) = 0\) 和 \(c(e) = 0, d(e) = 1\) 两种情况，分别递归求值。
2，通过异或让这一位上的数直接满足 \(a \oplus c < b \oplus d\)，我们钦定这个询问函数在执行第 \(e\) 位时比其高的位上的数都相等，所以应该满足 \(a(e) \oplus c(e) < b(e) \oplus d(e)\)，所以讨论取值有 \(c(e) = 0, d(e) = 0\)，通过 \(maxf_{(0,0)}\) 直接求值。
询问的元素对在第 \(e\) 位的种类为10即 \(a(e) = 1\)，\(b(e) = 0\) 时：
1，通过异或让这一位上的数相等，所以对应的 \((c, d)\) 应该有 \(a(e) \oplus c(e) = b(e) \oplus d(e)\)，所以分类讨论下一次递归询问分别有 \(c(e) = 1, d(e) = 0\) 和 \(c(e) = 0, d(e) = 1\) 两种情况，分别递归求值。
2，通过异或让这一位上的数直接满足 \(a \oplus c < b \oplus d\)，我们钦定这个询问函数在执行第 \(e\) 位时比其高的位上的数都相等，所以应该满足 \(a(e) \oplus c(e) < b(e) \oplus d(e)\)，所以讨论取值有 \(c(e) = 1, d(e) = 1\)，通过 \(maxf_{(1,1)}\) 直接求值。
询问的元素对在第 \(e\) 位的种类为11即 \(a(e) = 1\)，\(b(e) = 1\) 时：
1，通过异或让这一位上的数相等，所以对应的 \((c, d)\) 应该有 \(a(e) \oplus c(e) = b(e) \oplus d(e)\)，所以分类讨论下一次递归询问分别有 \(c(e) = 0, d(e) = 0\) 和 \(c(e) = 1, d(e) = 1\) 两种情况，分别递归求值。
2，通过异或让这一位上的数直接满足 \(a \oplus c < b \oplus d\)，我们钦定这个询问函数在执行第 \(e\) 位时比其高的位上的数都相等，所以应该满足 \(a(e) \oplus c(e) < b(e) \oplus d(e)\)，所以讨论取值有 \(c(e) = 1, d(e) = 0\)，通过 \(maxf_{(1,0)}\) 直接求值。
最后将两种不同的求值方式取最大值，返回，即为询问函数。
Q:
刚刚的询问函数因为每层都分了两类，所以最终的时间复杂度应该依然是单次询问 \(O(V)\)，其中 \(V\) 表示 \(a_i\) 的最大取值，所以过不了，这时怎么办？
A:
倒回到我们分的四种情况，发现四种情况里每次向下递归的两种小情况要么同时满足 \(c(e) = d(e)\)，否则同时满足 \(c(e) \neq d(e)\)，所以简化 Trie 树的分支情况，改为 \(c(e) = d(e)\) 和 \(c(e) \neq d(e)\) 两种情况的分支，\(maxf\) 的求值方式不变，但前缀由具体的4进制变为相等或不相等的比较后的2进制。
设 \(V\) 表示 \(a_i\) 的最大取值，这时插入的时间复杂度不变，仍然是单次 \(O(\log_{2}{V})\)，但查询的复杂度由每层分支两种情况变为每层分支唯一情况，所以时间复杂度优化为单次 \(O(\log_{2}{V})\)，可以通过此题。
Code：
#include <bits/stdc++.h>
using namespace std;
int n, a[300005], f[300005], Ans;
int l_trie;
struct trie {
int thr[2], maxf[4];
void clear (){
for (int i = 0;i < 2;++ i)
thr[i] = - 1;
for (int i = 0;i < 4;++ i)
maxf[i] = - 1;
}
trie (){
for (int i = 0;i < 2;++ i)
thr[i] = - 1;
for (int i = 0;i < 4;++ i)
maxf[i] = - 1;
}
}tr[9000005];
int get_b (int a, int p){
return (a >> p) & 1;
}
int get_tr (int p, int opts){
return tr[p].maxf[opts];
}
int Query (int p, int b, int c, int e){
if (p == - 1 || e < 0)
return - 1;
int tpsb = get_b (b, e), tpsc = get_b (c, e);
if (tpsb == tpsc){
int Res = - 1;
if (tpsb == 0)
Res = max (Res, get_tr (p, 1));
if (tpsb == 1)
Res = max (Res, get_tr (p, 2));
Res = max (Res, Query (tr[p].thr[0], b, c, e - 1));
return Res;
}
if (tpsb != tpsc){
int Res = - 1;
if (tpsb == 0)
Res = max (Res, get_tr (p, 0));
if (tpsb == 1)
Res = max (Res, get_tr (p, 3));
Res = max (Res, Query (tr[p].thr[1], b, c, e - 1));
return Res;
}
}
void Push (int p, int b, int c, int e, int cs){
if (e < 0)
return ;
int tpsb = get_b (b, e), tpsc = get_b (c, e), tps, to;
tps = (tpsb << 1) + tpsc;
to = tpsb ^ tpsc;
tr[p].maxf[tps] = max (tr[p].maxf[tps], cs);
if (tr[p].thr[to] < 0)
tr[p].thr[to] = ++ l_trie;
Push (tr[p].thr[to], b, c, e - 1, cs);
}
int main (){
int T;
scanf ("%d", &T);
while (T --){
scanf ("%d", &n);
for (int i = 1;i <= n;++ i){
scanf ("%d", &a[i]);
f[i] = max (0, Query (0, i - 1, a[i], 30)) + 1;
Ans = max (Ans, f[i]);
Push (0, a[i], i - 1, 30, f[i]);
}
printf ("%d\n", Ans);
for (int i = 0;i <= l_trie;++ i)
tr[i].clear ();
l_trie = 0;
Ans = 0;
}
return 0;
}