线性表出

对于一个空间中的向量来说，如果向量集合中的一些向量只进行加法和数乘运算可以得到另一个向量，则称这个向量可以由这个集合中的向量 线性表出 。如果一组向量中任意一个向量都不能被其他向量线性表出，则称这一组向量 线性无关 ，否则成为 线性相关 。

线性空间的基

如果一个线性空间可以由一组向量 张成 ，并且这一组向量线性无关，则称这一组向量是线性空间的一个 基 ，基中的向量个数叫做这个向量空间的 维度 。基的任何子集都不能张成原向量空间，原向量空间可以有多个基，每个基中向量个数相同。 原线性空间的一个向量可以由基中的向量唯一表出 。

异或线性基

将每个数的二进制表示看作向量构成的向量空间的基。

基中元素张成的空间等价于原空间，即基中的数相互异或形成的集合等价于原数相互异或形成的集合。

线性基二进制最高位互不相同。一个满的线性基（每一位都有数）表示的异或集合为 $[1,2^n-1]$

维护

维护一个上三角矩阵，即最高位互不相同。

插入

对于这个数的是一的每一位，判断在原线性基中这一位是否有数，如果没有，就把这个数加到线性基的这一位，如果有，就把这一位上的一消掉，也就是说始终保持比当前位高的位均为 $0$ ，这样插入时仍能保证上三角矩阵。

注意要打一个 $tag$ 标记表示异或线性基能否组合出 $0$ 。能组合出 $0$ 当且仅当有一个数在插入时被削成了 $0$ 。

void insert(ll a)

{

	for(int i = BASE;i >= 0;--i)

	{

		if(a & (1ll << i))

		{

			if(d[i] == 0)

			{

				++cnt;

				d[i] = a;

				break;

			}

			else a ^= d[i];

		}

	}

	if(a == 0)tag = true;

	return;

}

查询异或最大值

由于最高位各不相同且任意两个基相互不影响，故查询满足贪心性质，逐位考虑如果异或上这个基可以使结果更大，就把这位异或上。

ll query_max()

{

	ll res = 0ll;

	for(int i = BASE;i >= 0;--i)

	{

		if((res ^ d[i]) > res)res ^= d[i];

	}

	return res;

}

查询异或最小值

如果 $tag$ 为真，则最小值是 $0$ 。否则由线性基的性质可知最小值为最小的那个线性基。

ll query_min()

{

	if(tag)return 0;

	for(int i = 0;i <= BASE;++i)

	{

		if(d[i])return d[i];

	}

	return 0;

}

查询第 $k$ 小值

先把能消掉的位都削成 $0$ ，保证每一次异或操作都能得出更大的答案，存储到一个数组里。注意数组循环的方向，从 $0$ 位开始填数。

void prepare()

{

	int tot = 0;

	memset(p,0,sizeof(p));

	for(int i = BASE;i >= 0;--i)

	{

		for(int j = i - 1;j >= 0;--j)

		{

			if(d[i] & (1ll << j))

			{

				d[i] ^= d[j];

			}

		} 

	}

	for(int i = 0;i <= BASE;++i)

	{

		if(d[i])

		{

			p[tot++] = d[i];

		}

	}

	return;

}

然后先判断异或集合中是否存在 $0$ ，如果存在，则 $--k$ ，由于线性基中的数最高位都不同，所以共能组成 $2^n-1$ 个数，由二进制的性质可得以第 $i$ 大的线性基开头的数由 $2^{i-1}$ 个（后 $i-1$ 个线性基可以随意组合），于是逐位考虑 $k$ 的每个二进制位，如果这位是一，就说明有 $2^{i-1}$ 个比他小的，于是答案就异或上第 $i$ 个线性基。类似数位 $DP$ 。

ll query_kth(ll k)

{

	if(tag){--k;}

	ll res = 0;

	if(k >= (1ll << cnt))return -1;

	for(int i = BASE;i >= 0;--i)

	{

		if(k & (1ll << i))

		{

			res = res ^ p[i];

		}

	}

	return res;

}

查询 $k$ 的排名

查询数字 $k$ 再张成的集合中排名第几。

对于一个再张成集合中的数，他一定出现了 $2^{n-cnt}$ 次，因为有 $n-cnt$ 个向量被线性表出了，它们之间可以任意组合一定还能找到一组基底使得异或出这个数。还是先 $prepare$ ，不过略有不同，如果第 $i$ 位线性基上有值，那么就能组合出以他为开头的 $2^{i-1}$ 个数，所以先把所有有数的线性基找出来并记下位数。

void prepare()

{

	tot = 0;

	memset(p,0,sizeof(p));

	for(int i = 0;i <= BASE;++i)

	{

		if(d[i])

		{

			p[tot++] = i;

		}

	}

	return;

}

对于一个查询的 $k$ ，如果线性基 $i$ 位数为 $j$ ，且 $k$ 第 $j$ 位上有值，那么就有了 $2^j$ 个数比他小，故 $ans+=2^j$ ，最后由于每个数都出现了 $2^{n-cnt}$ 次，再乘上即可。

ll query_krank(ll k)

{

	int res = 0;

	for(int i = 0;i < tot;++i)

	{

		if(k & (1ll << p[i]))

		{

			res += (1 << i);

			res %= MOD;

		}

	}

	res = (res * power(2,n - cnt) % MOD + 1) % MOD;

	return res;

}