D2. Xor-Subsequence (hard version)
/*
进行转换,可以要存储i^a[i]的值
首先确保前面都是相同的
然后假设下一位是不相同的,那么会在这里进行更新,都枚举一下就可以了
字典树+dp
也就是看跳到某一位后进行更新就可以了
复杂度是可以接受的
*/
#include <bits/stdc++.h>
using namespace std;
const int M=3e5+5;
int ch[M*32][2],f[M*32][2],tot;
int a[M];
void insert(int x,int y,int mx) {//更新
int p=0;
for(int i=30;i>=0;i--) {
int u=x>>i&1,v=y>>i&1;
if(!ch[p][u^v])ch[p][u^v]=++tot;
p=ch[p][u^v];
f[p][u]=max(f[p][u],mx);//在这个点的时候,我是取u的
}
}
int query(int x,int y) {//查找
int p=0,mx=0;
for(int i=30;i>=0;i--) {
int u=x>>i&1,v=y>>i&1;
//假设这里是转折点,也就是下一位开始就不相同了,那么要怎么进行更新
//枚举所有的情况,一共四种
if(u!=v) {
if(ch[p][0]) {
if(u==1)mx=max(mx,f[ch[p][0]][1]);
else mx=max(mx,f[ch[p][0]][0]);
}
}
else {
if(ch[p][1]) {
if(u==1)mx=max(mx,f[ch[p][1]][0]);
else mx=max(mx,f[ch[p][1]][1]);
}
}
p=ch[p][u^v];
if(!p)break;
}
return mx+1;
}
void solve() {
int n;cin>>n;
int ans=0;
for(int i=0;i<n;i++) {
cin>>a[i];
int mx=query(i,a[i]);
ans=max(ans,mx);
insert(i,a[i],mx);
}
cout<<ans<<endl;
for(int i=0;i<=tot;i++)ch[i][0]=ch[i][1]=f[i][0]=f[i][1]=0;
tot=0;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int TT;cin>>TT;
while(TT--)solve();
return 0;
}
标签:ch,Xor,int,max,hard,else,Subsequence,mx
From: https://www.cnblogs.com/basicecho/p/17233308.html