01trie 的简单应用
EnofTaiPeople
·
·
题解
讲的是 CF1720D2。
简要题意：
有 t 组数据，对于每组数据，给定 n 和 a_0,...,a_{n-1}，均为自然数，求一个最长的自然数列 b_i，设其长度为 m 需要满足 0\le b_1<...<b_m<n 且 \forall i\in[1,m),a_{b_i}\otimes b_{i+1}<a_{b_{i+1}}\otimes b_i。
容易发现这是一个动态规划的模型，我们需要找到 $\max\limits_{j<i,a_j\otimes i<a_i\otimes j}f_j$，由于只有位运算，不难想到按位考虑。
从高到低考虑每一位，如果 $a_j\otimes i$ 和 $a_i\otimes j$ 在该位相同，这等价于 $a_j\otimes j$ 与 $a_i\otimes i$ 在该位相同，就继续下一位，否则一定是 $a_i\otimes j$ 在这一位为一。
将 $i$ 从小到大计算，在求出 $f_i$ 后，可以将 $a_i\otimes i$ 插入到一棵 $\text{01trie}$ 内，对于每一个节点记录 $i$ 在上一位为一的最大值，和为零的最大值。
查询就顺着 $a_i\otimes i$ 走 $\text{01trie}$，沿途处理相反方向的答案（即该位不同的情况）。
不到 1k 的 AC 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
using ll=long long;
ll A,B,C,D;
ll T,n,m,f[N],a[N];
int t[N<<4][2],mx[N<<4][2],ans;
inline void Mx(int &x,int y){if(x<y)x=y;}
int cnt,rt,v1,v2,v3,nw;
void ins(int &x,int w=31){
if(!x)x=++cnt;
int p=v1^v2;
Mx(mx[x][(v2>>w)&1],v3);
if(w--)ins(t[x][(p>>w)&1],w);
}
void qry(int &x,int w=31){
if(x&&w--){
int k=((v1^v2)>>w)&1;
Mx(nw,mx[t[x][!k]][((v1>>w)&1)^1]);
qry(t[x][k],w);
}
}
int main(){
int i,j,k,l,md,r;
ios::sync_with_stdio(false);
cin>>T;while(T--){
for(i=1;i<=cnt;++i)
mx[i][0]=mx[i][1]=t[i][0]=t[i][1]=0;
cin>>n,ans=cnt=rt=0;
for(i=1;i<=n;++i)cin>>a[i];
for(i=1;i<=n;++i){
v1=a[i],v2=i-1,nw=0,qry(rt);
Mx(ans,v3=f[i]=nw+1),ins(rt);
}printf("%d\n",ans);
}return 0;
}
```