526互联

01trie

发布时间 2023-12-20 11:46:16作者: hubingshan
struct TRIE{
	int tot;
	int ch[N*31][2];
	TRIE(){memset(ch,0,sizeof(ch));tot=1;}
	void insert(int x){
		int p=1;
		for(int i=29;i>=0;i--){
			int c=(x>>i)&1;
			if(!ch[p][c]) ch[p][c]=++tot;
			p=ch[p][c];
		}
	}
	int find(int x){
		int p=1,ans=0;
		for(int i=29;i>=0;i--){
			int c=(x>>i)&1;
			if(ch[p][c]) p=ch[p][c];
			else p=ch[p][c^1],ans|=(1<<i);
		}
		return ans;
	}
	void clear(){
		while(tot) ch[tot][0]=ch[tot][1]=0,tot--;
		tot=1;
	}
}T;