转自https://www.luogu.org/blog/Marser/solution-p3812

首先，线性基是用于查询多个数中选取一些数的Xor最大值,最小值,以及能否得到某个值的数据结构，可以在log的时间内解决问题。

它实际上是一个大小为log的数组,对于每一位记录一个最高位为它的某个数,要求这个数组可以表示所有这些数的子集的Xor值,初始全部为零。

插入和判断

插入数u时,从高位到低位遍历,如果u的这一位有值,则进行判断,若数组的这一位还没有数,则改为u并且break,否则u^数组中的这个数(详见代码),这样操作之后u只有两种结果:

  1. 被记录到了数组中

  2. 未被记录,则此时u必定为0,说明此时的线性基已经能通过Xor得到u.

因此我们可以用这种方法来判断此时是否存在Xor值为u的子集.

void ins(long long x){
    for(int i=maxlog;i>=0;i--)
        if(x&(1ll<<i))
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
}
bool check(long long x){
    for(int i=maxlog;i>=0;i--)
        if(x&(1ll<<i))
            if(!a[i])return 0;
            else u^=a[i];
    return 1;
}

查询最值

最大值可以用贪心的思想来做。

从高到低遍历数组,如果ans^第i位的那个数后大于ans,则^这个数,因为这样可以保证ans第i位为1,且后面不可能有机会改变第i位。

很显然，数组中最小的非零数就是最小值。

查询第k小值

首先将数组中的所有数变成包含这个最高位且可以通过Xor得到的最小值。

具体实现方法就是每一位向后扫,若Xor后变小,则Xor。

之后就可以发现第k小只要将k改为二进制后,将二进制所对应的位置的数Xor起来即可。

long long qmax(){
    long long res=0;
    for(int i=maxlog;i>=0;i--)if((res^a[i])>res)res^=a[i];
    return res;
}
long long qmin(){
    for(int i=0;i<=maxlog;i++)if(a[i])return a[i];
}
long long query(int k){
    long long tmp[maxlog+1],res=0;int cnt=0;
    for(int i=0;i<=maxlog;i++){
        for(int j=i-1;j>=0;j--)if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[cnt++]=a[i];
    }
    for(int i=0;i<cnt;i++)if(k&(1ll<<i))res^=tmp[i];
    return res;
}

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
template<typename T>struct linear_base{
    static const int maxlog=60;
    T a[61];
    void ins(T x){
        for(T i=maxlog;i>=0;i--)
            if(x&((T)(1)<<i))
                if(!a[i]){a[i]=x;return;}
                else x^=a[i];
    }
    bool check(T x){
        for(T i=maxlog;i>=0;i--)
            if(x&((T)(1)<<i))
                if(!a[i])return 0;
                else x^=a[i];
        return 1;
    }
    T qmax(){
        T res=0;
        for(T i=maxlog;i>=0;i--)if((res^a[i])>res)res^=a[i];
        return res;
    }
    T qmin(){
        for(T i=0;i<=maxlog;i++)if(a[i])return a[i];
    }
    T query(int k){
        T tmp[maxlog+1],res=0,cnt=0;
        for(T i=0;i<=maxlog;i++){
            for(int j=i-1;j>=0;j--)if(a[i]&((T)(1)<<j))a[i]^=a[j];
            if(a[i])tmp[cnt++]=a[i];
        }
        for(T i=0;i<cnt;i++)if(k&((T)(1)<<i))res^=tmp[i];
        return res;
    }
};
linear_base<ll>s;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){ll x;scanf("%lld",&x);s.ins(x);}
    printf("%lld\n",s.qmax());
    return 0;
}