线性基

线性基三大性质

1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到

2.线性基里面的任意一些数异或起来都不能得到；

3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

一、定义

首先什么是线性基呢？对于一组数 A1...An，他们的线性基为 P1...Pm ，其中 Pi 是出现 1 的最高位在第 i 位的数 。很容易想到，线性基的值域与原数组的值域相同。那么我们便可以通过线性基来求最大异或和。

二、构造方法

对于每一个数，我们找出他的最高位的 1 在第 i 位，如果此时 Pi 为零，就将这个数加入线性基，否则异或 Pi 继续找。然后我们就可以在 0 到 k 位上处理好每一位的线性基。这样得到的线性基保证每一位都能有对应的最大值。

#include <cstdio>
#include <iostream>
using namespace std;
long long p[100];
long long a[60];
void pre(long long x)
{
    for(int i=60;i>=0;i--){
        if((x>>i)==0) continue;
        if(p[i]==0){
            p[i]=x;
            break;
        }
        x^=p[i];
    }
}
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre(a[i]);
    long long ans=0;
    for(int i=60;i>=0;i--){
        if(ans<(ans^p[i])){
            ans=ans^p[i];
        }
    }
    cout<<ans;
    return 0;
}

三、寻找答案

如何求最大值：

在我们得到的线性基中，从高位到低位用贪心贪掉每一个元素（即如果异或了这个元素变大就异或他）

如何求最小值：

显然的，最小值一定是最小的线性基；

四、查询某个数

把它尝试插入进线性基里面去，假如可以插入，说明不能异或得到，假如插不进去，则说明可以异或得到。

五.合并

合并两个线性基只需要把一个线性基暴力插入另一个即可，复杂度：线性基大小*插入复杂度；

六.删除

像我这种蒟蒻写出来的菜鸡线性基根本就不支持删除操作。但删除操作确实是可以做的；

七.求取第k小值：

乍一看，一般的线性基好像不可做，
问题在哪儿？
1000001
0000001
同时选1和2比只选1要差，所以我们无法做

但是如果线性基长成这样
1000000
0100000
0010000
0001000
0000100
那么就好做了，因为选取1和2一定比只选1要优。

所以我么需要对原来的线性基rebuild一下，使得它变成上面那样的形式，当然
1000010
0100001
0000101
这种形式也是可以的，最后一位上没有数，所以同时选2和3也比只选2优，尽管最后一位上的1被消掉了
所以我们要使得若p[i]!=0，那么线性基里其他的数第i位上都为0，所以我们只需要拿p[i]去xor一下那些数就好了。
rebuild之后的线性基怎么做：把k转成二进制，若k的第i位为1，那么将ans xor 上rebuild后第i大的p就行了。

void rebuild()
{
    for (int i=60;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<=60;i++)
        if (d[i])
            p[cnt++]=d[i];
}
long long kthquery(long long k)
{
    int ret=0;
    if (k>=(1LL<<cnt))
        return -1;
    for (int i=60;i>=0;i--)
        if (k&(1LL<<i))
            ret^=p[i];
    return ret;
}