线性基

所谓线性基，就是线性空间的一组基。基是线性空间的极大线性无关组。

OI 中的线性基一般指异或线性基。对于实数线性基，我们习惯用高斯消元来称呼它。在题目中，线性空间中的向量一般是以数的形式出现的，可以把它们二进制分解后看成向量，比如 \(5 \to [1,0,1]\)。在这种情况下，向量组线性无关就是指组中任意一个向量都不能被其它几个向量异或表示出来。

比如，\(1,2,3\) 所张成的线性空间的一组基为 \(\{1,2\}\)，因为 \(1\) 和 \(2\) 都不能被组中其它向量表出，而 \(3\) 可以被 \(1\) 和 \(2\) 表出。

求解线性基

我们不断地插入向量。贪心地想，我们从高到低给每一位选主元。如果这一位没有主元，就将这个向量作为这一位的主元。如果有主元了，就把这个向量异或上主元，然后继续往下插入。

容易发现这和高斯消元的过程类似，事实上，它们本质相同。

	int p[N];
	inline void Insert(int x){
		for(int i=N-3;i>=0;--i){
			if(!(x&(1ll<<i)))
				continue;
			if(!p[i]){
				p[i]=x;
				return;
			}else{
				x^=p[i];
			}
		}
		return;
	}

性质

按照上述方法构造出来的线性基满足以下性质：

• 其中没有异或和为 \(0\) 的元素。

  显然。

• 其张成的线性空间大小为 \(2^s\)，其中 \(s\) 是线性基的大小。

  考虑只有有主元的位能够决定这一位是 \(0\) 还是 \(1\)，其它的位的取值是固定的。

应用

• 给定 \(x\)，求在某一堆数中选若干个和 \(x\) 异或起来的最大异或和

  把那一堆数建线性基，然后从高到低贪心，如果这一位有主元并且异或上主元更大，就异或

• 求线性基能表出的最大值

  等价于和 \(0\) 异或。

• 合并两个线性基 \(A,B\)

  把 \(B\) 中的元素逐个插入 \(A\) 即可。注意到插入线性基中元素（被异或处理之后的）就可以了，不一定需要插入原数。

  正确性显然。

• 可删除线性基

  需要离线。

  第一种做法：线段树分治。

  第二种做法：在每一位维护值的前提下，再维护一个最晚删除时间。对于插入操作，从高到低每一位取最后删除的。

  int cur=read(),val=read();
  for(int i=30;i>=0;--i){
      if(!(val&(1<<i))) continue;
      if(time[i]<cur) std::swap(time[i],cur),std::swap(p[i],val);
      val^=p[i];
  }