线性基

刚认识这个东西，还以为有多么高大上呢

定义

OI-Wiki版

称线性空间 $V$ 的一个极大线性无关组为 $V$ 的一组 Hamel 基 或 线性基，简称 基。
规定线性空间 ${\theta}$ 的基为空集。
另外，将 $V$ 的 维数 记作 $\dim V$, 定义为基的元素个数。

更通俗易懂一点的版本

线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。

性质

1. 原序列里面的任意一个数都可以由线性基里面的一些数异或得到
2. 线性基里面的任意一些数异或起来都不能得到$0$
3. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

操作

构造（插入一些数并判断）

令插入的数为$x$,考虑$x_{(2)}$进制下的最高位$i$

• 若线性基的第$i$位为$0$,则直接在该位插入$x$,退出；
• 若线性基的第$i$位已经有值$a_i$，则$x=x\bigoplus a_i$，重复以上操作直到$x=0$

如果退出时$x=0$,则此时线性基已经可以表示原先的$x$了；反之，则说明为了表示$x$，插入了一个新元素。

可以证明，时间空间复杂度均为$O(\log_2x)$

void insert(long long x){
    for(int i = max_bit;~i;i--){
        if(x&(1LL<<i)){//注意，如果max_bit大于31，一定要写成1ll
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
        }
    }
    flag=true;//表示当前树数已经能够被线性基表示，也就是说有两个一样的数
    //若下方不涉及最值运算，可不记录
}
bool check(long long x){
    for(int i = max_bit;~i;i--){
        if(x&(1LL<<i)){
            if(!a[i]) return false;
            else x^=a[i];
        }
    }
    return true;
}

异或最值

最小值

考虑插入的过程，$x$的二进制最高位必定单调降低，所以不可能插入两个二进制最高位相同的数。而此时，线性基中最小值异或上其他数，必定会增大。所以，直接输出线性基中的最小值即可。

long long qmin(){
    long long ans=0;
    if(flag) return 0;
    for(int i = 0;i<=max_bit;i++){
        if(a[i]) return a[i];
    }
}

最大值

从高到低遍历线性基，考虑到第$i$位时，如果当前答案$ans$的第$i$位为$0$，就将$ans$异或上$a_i$，否则不做操作。这样，每次操作后的答案不会变劣，得到最终答案。

long long qmax(){
    long long ans=0;
    for(int i = max_bit;~i;i--){
        ans=max(ans,ans^a[i]);
    }
    return ans;
}

第$k$小值

注意，这里的第k小值是指异或出来的数的第k小

• 对于每一个$a_i$,枚举$j = i \ \ to \ \ 1$,如果${d_i}{(2)}$的第$j$位为$1$，那么$d_i = d_i \bigoplus d{j-1}$
• 若$k_{(2)}$的第$i$位为$1$，$ans$就异或上处理后的线性基中第$i$个元素。

long long k_th(long long k){
    long long res=0,cnt=0;
    k-=flag;if(!k) return 0;
    for(int i = 0;i<=max_bit;i++){
        for(int j=i-1;~j;j--){
            if(a[i]&(1LL<<j))a[i]^=a[j];
        }
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1LL<<cnt)) return -1;
    for(int i = 0;i<cnt;i++){
        if(k&(1LL<<i))res^=tmp[i];
    }
    return res;
}