线性基

用于维护异或的数据结构。（又是模拟赛保龄过来补）

废话多不多说了，直接上正题。

先说什么是线性基吧。()

就是说对于一个集合，如何它对于异或在线性基集合中封闭。那么我们认为之歌构造出的集合是线性基。对于异或封闭是什么意思？就是说它内的元素异或来异或去就只会得出原集合的东西。

怎么构造？

考虑对于每一个数，我们考虑从高到低枚举数位，然后对于这一位没有数的数位，直接把当前数放到这一位中，否则我们异或上这一位的数，然后只需枚举数位。

Code:

inline void ins(LL x){
	for(int i=63;i>=0;--i){
		if(!((x>>i)&1)) continue;
		if(!p[i]){
			p[i]=x;break;
		}
		x^=p[i];
	}
}

注意这里我们不能i从64开始，因为这样会爆掉（$long\ long$ 是 $2^{64}-1$）

查询操作

我们求可选的数中能够异或而得到的最大值。

类似 $01trie$ 的一个做法，考虑这一位上的数如果异或上初始值为 $0$ 的答案得到一个更大的数就取，否则不取。还是从高位开始往低位扫，因为高位的 1 比低位 1 的和还大。

Code:

inline LL query_max(){
	LL ans=0;
	for(int i=63;i>=0;--i){
		if(!p[i]) continue;
		if((ans^p[i])>ans) ans^=p[i];
	}
	return ans;
}