60pts 2xTLE 字典树求助
查看原帖
60pts 2xTLE 字典树求助
1173109
OrientDragon楼主2024/12/24 14:35
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,cnt=1,a[N];
struct Trie{
	int son1,son0,ans;
	Trie(){
		son1=son0=ans=0;
	}
	int s1(){
		if(son1)return son1;
		son1=++cnt;
		return son1;
	}
	int s0(){
		if(son0)return son0;
		son0=++cnt;
		return son0;
	}
}t[N];
void upd(int x){
	if(!t[x].son1&&!t[x].son0)return;
	upd(t[x].son1);
	upd(t[x].son0);
	t[x].ans=t[t[x].son1].ans+t[t[x].son0].ans;
}
void push(int x){
	int now=1;
	for(int k=30;k>=0;k--){
		if(x&(1<<k))now=t[now].s1();
		else now=t[now].s0();
	}
	t[now].ans++;
	upd(1);
}
int find(int x){
	int ret=0,now=1;
	for(int k=30;k>=0;k--){
		if(!t[now].son1)now=t[now].s0();
		else if(!t[now].son0)now=t[now].s1(),ret|=(1<<k);
		else if(x&(1<<k))now=t[now].s1(),ret|=(1<<k);
		else now=t[now].s0();
	}
	return ret;
}
int solve(int x[N]){
	int mx=0;
	push(x[1]);
	for(int i=2;i<=n;i++){
		int inv=2147483647-x[i];
		mx=max(mx,x[i]^find(inv));
		push(x[i]);
	}
	return mx;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cout<<solve(a);
}

这个字典树是瞎写的(

提交记录

2024/12/24 14:35
加载中...