T2 CF 2093G Shorten the Array
原题链接
本着不轻易上算法的原则想了半天，最后还是 01 trie 做完了。
如果只要求异或和为 \(k\) ，就可以用 map 维护每个数出现的最晚的位置，根据异或的性质直接查找需要的数字，统计答案即可。
但这题的条件为大于等于 \(k\)，多了大于的条件，不太好直接用异或求解需要的数，考虑拆位维护，又因为需要对多个数字同时统计，考虑 01 trie。
因为这题要求的是最短的子数组长度，实际上就是求一对符合要求的数字，并且最近，所以在 01 trie 上要维护每个数字的位置信息，处理一次查询的操作如下：
从高到低地去比较 \(k\) 的每一位和 trie 上的每一位，如果能比 \(k\) 大则说明当前点子树里所有的数字都符合条件，则最优答案为这些数中最靠后的那个，否则尽量与 \(k\) 保持一致，否则无解。
故我们在 01 trie 上维护当前点的子树中，所有数的 \(id\) 的最大值即可。
const int N=2e5+5;
int T;
int n;
int a[N],k;
int t[N*30][2],pos[N*30],cnt;
void clear(){for(int i=0;i<=cnt;i++){t[i][0]=t[i][1]=pos[i]=0;}cnt=0;
}
void insert(int x,int id){int rt=0;for(int i=30;i>=0;i--){bool now=(x&(1<<i));if(!t[rt][now]) t[rt][now]=++cnt;rt=t[rt][now];pos[rt]=max(pos[rt],id);}
}
int query(int x){int rt=0,res=-1;for(int i=30;i>=0;i--){int x_bit=((x>>i)&1);int k_bit=((k>>i)&1);if(k_bit==1){if(!t[rt][x_bit^1]){return res;}rt=t[rt][x_bit^1];}else {if(t[rt][x_bit^1]){res=max(res,pos[t[rt][x_bit^1]]);}if(!t[rt][x_bit]){return res;}rt=t[rt][x_bit];}}res=max(res,pos[rt]);return res;
}
void xpigeon(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}if(k==0){cout<<1<<'\n';return ;}int ans=1e18;clear();for(int i=1;i<=n;i++){insert(a[i],i);int res=query(a[i]);if(res!=-1) ans=min(i-res+1,ans);}if(ans==1e18){cout<<-1<<'\n';}else{cout<<ans<<'\n';}
}
signed main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>T;while(T--) xpigeon();return 0;
}