基本

对于一个值域为1-N的集合S

它的线性基的值域与S相同

它的线性基中的元素个数小于等于logN

集合S中任意数异或和存在于线性基中

线性基任意数异或和存在于集合S中

插入

首先，线性基大体长这样

XXXXX 称为第[线性基中数的个数]个数

口XXXX

口口口XX

口口口口X 称为第1个数

d[i]和“线性基中第i个数”不是同一概念，注意辨析

将一个数x插入线性基成为一次插入

对于每次插入，从高到低枚举x的每一个二进制位，每一次枚举称为一次判断

对于每次判断，分三种情况讨论

1.x的第i位是0：continue掉这次判断

2.d[i]是空的：直接把d[i]变为x，结束插入

3.x的第i位是1且d[i]不是空的：x^=d[i]

void Insert(ll x)
{
	for(ll i=64;i>=1;i--)
	{
		if(!x) return ;
		if(!((x>>(i-1))&1)) continue;
		if(!d[i])
		{
			d[i]=x;
			total++;//线性基里一共有几个数
			return ;
		}
		else x^=d[i];
	}
}

查询异或最值

求集合S任意数异或最小值/最大值

最小值

分两种情况讨论：

1.线性基大小小于|S|：说明S中一定可以异或出0 最小异或和为0

2.线性大小等于|S|：显然，最小值为线性基中最小的数(无论怎么异或都会使值变大)，从线性基的第1个位置往低N个位置枚举，直到一个有数的位置，这个数即为最小异或和

最大值

答案初始值为d[n]

从n-1到1枚举线性基中每一个数，如果答案异或这个数可以使答案变大，那么答案异或这个数，枚举完后的答案即为集合S异或最大值

查询第K小值

首先对线性基进行改造

具体地，先枚举i，再枚举j（从i-1到1）

如果d[i]的第j位为1，那么d[i]^=d[j]

显然，这样改造后的线性基仍是原S集合的线性基

void Remodle()
{
	for(ll i=64;i>=1;i--)
	{
		for(ll j=i-1;j>=1;j--)
		{
			if((d[i]>>(j-1))&1) d[i]^=d[j];
		}
	}
}

而改造后的线性基大概长这样

1XXXX0XXX0X

000001XXX0X

00000000001X

所以又很显然（不会证，但是可以感觉出来）

令ans=0

假如询问的k的第i位为1，ans^=线性基中第i个数

最终ans即为第k小值

for(ll i=1;i<=64;i++) 
	{
		if(d[i])
		{ 
			if(k%2) ans^=d[i];
			k/=2;
		}
	}

查询x的排名

一样的，先改造线性基

从n枚举到1

如果x大于d[i]，ans+=(1ull<<d[i]是线性基中第几个数-1) 并且 x^=d[i]

x即为线性基所有异或和中第ans小的数

ll cnt=total;//线性基里一共有几个数
for(ll i=64;i>=1;i--)
{
	if(d[i])
	{
		if(x>=d[i]) ans^=(1ull<<(cnt-1)),x^=d[i];
		cnt--;
	}
}

删除[待填坑]