CF1720D

字典树+dp，非常interesting

#include <bits/stdc++.h>
 /*
 #include<ext/pb_ds/assoc_container.hpp>
 #include<ext/pb_ds/hash_policy.hpp>
 */
 using namespace std;
 
 const double eps = 1e-10;
 const double pi = 3.1415926535897932384626433832795;
 const double eln = 2.718281828459045235360287471352;
 
 #define f(i, a, b) for (int i = a; i <= b; i++)
 #define scan(x) scanf("%d", &x)
 #define mp make_pair
 #define pb push_back
 #define lowbit(x) (x&(-x))
 
 #define fi first
 #define se second
 #define SZ(x) int((x).size())
 #define all(x) x.begin(), x.end()
 #define rall(x) x.rbegin(), x.rend()
 #define summ(a) (accumulate(all(a), 0ll))
 
 typedef unsigned long long ull;
 typedef pair<int,int> pii;
 typedef vector<int> vi;
 
 using ll=long long;
 struct trie{
    vector<array<int,2>> ch;
    vector<array<array<int,2>,2>> val;
    trie(){ch.resize(1),val.resize(1);}
    void insert(int ai,int i,int dpval){
        bitset<30> b1(ai),b2(i);
        int now=0;
        for(int k=29;~k;--k){
            val[now][b1[k]][b2[k]]=max(val[now][b1[k]][b2[k]],dpval);
            if(ch[now][b1[k]^b2[k]]==0){
                val.push_back({0,0,0,0});
                ch.push_back({0,0});
                ch[now][b1[k]^b2[k]]=val.size()-1;
            }
            now=ch[now][b1[k]^b2[k]];
        }
    }
    int query(int aj,int j){
        int now=0,ans=0;
        bitset<30> b1(aj),b2(j);
        for(int k=29;~k;--k){
            int i=!b1[k],ai=b2[k];
            ans=max(ans,val[now][ai][i]);
            now=ch[now][b1[k]^b2[k]];
            if(!now)break;
        }
        return ans;
    }
};

 int tt,n;

 int main()
 {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(Sb,1,tt){
        cin>>n;
        vi v(n);
        for(auto &it:v)cin>>it;
        trie t;
        int ans=0;
        for(int i=0;i<n;++i){
            int tmp=t.query(v[i],i);
            t.insert(v[i],i,tmp+1);
            ans=max(ans,tmp+1);
        }
        cout<<ans<<"\n";
    }
    return 0;
}