真的恶心，妈的放道D1恶心人，D1跟D2正解毛关系都没有，傻逼比赛
题号 CF1720D2 Xor-Subsequence (hard version)
简单转化一下题意就是求这样的一个
dp数组：
\(f[i]=max_{a[i]⊕j>a[j]⊕i}(f[j]+1)\)
以前看见异或不等完全不敢在不等号两边操作，然后这题就是要在不等号上操作：
- 先考虑对这个不等式变换，先把 \(i,j\) 分离，这是个常用套路：
- 变成 \((x[i]=a[i]⊕i)⊕(i⊕j)>(x[j]=a[j]⊕j)⊕(i⊕j)\)，这样式子的运算本质上就被统一了（感性理解一下，因为左右两边同时异或上一个相等的数），然后考虑怎么去除 \((i⊕j)\)
考虑模拟二进制比较，就是先求出 \(x⊕y\) 的值，看看在最高位的 \(1\) 上谁大谁小。那么假如我原先知道 \(x,y\) 的大小关系、他们最高在哪一位不同，那么如果我同时给 \(x,y\) 异或的数 \(t\) 在那位的值为 \(1\) 那么大小关系反转，反之亦然，那么我就可以枚举 \(x[i],x[j]\) 在哪一位是不同的，这个可以放在
01trie上搞，假如我枚举到第 \(k\) 位是不同的，那么我本质上只关心这些 这棵子树中有多少 \(j\) 异或上 \(i\) 后第 \(k\) 位为 \(0/1\) ，这些 \(j\) 的最大值是多少，由于我只关心这一位，和别的位毛关心都没有，那么我直接在01trie树上多记一个tag来将这棵子树中的 \(j\) 按照这一位的 \(0/1\) 来分类，然后就差不多了。
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=3e5+5,C=60,_log=30;
int trie[N*C][2],val[N*C][2],f[N],n,pool,ans;
void clear(){
for(int i=1;i<=pool;++i){
trie[i][0]=trie[i][1]=0;
val[i][0]=val[i][1]=0;
}
pool=1;
}
void modify(int x,int y,int df){
int p=1;
for(int i=_log;i>=0;--i){
int cx=(x>>i)&1,cy=(y>>i)&1;
if(!trie[p][cx])trie[p][cx]=++pool;
val[trie[p][cx]][cy]=max(val[trie[p][cx]][cy],df);
p=trie[p][cx];
}
}
int query(int x,int y){
//值为x，下标为y
int ret=0,p=1;
for(int i=_log;i>=0;--i){
int cx=(x>>i)&1,cy=(y>>i)&1;
if(cx)ret=max(ret,val[trie[p][0]][cy]);
else ret=max(ret,val[trie[p][1]][!cy]);
p=trie[p][cx];
}
return ret;
}
void solve(){clear();
n=read(),ans=0;
for(int i=0;i<n;++i){
int x=read()^i;
f[i]=query(x,i)+1;
modify(x,i,f[i]);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
}
int main(){
// freopen("C:\\Users\\root\\Desktop\\OI\\indata.txt","r",stdin);
// freopen("C:\\Users\\root\\Desktop\\OI\\outdata.txt","w",stdout);
int T=read();
while(T--)solve();
return 0;
}