发布时间：2024-09-09

概念

线性基是针对某个序列生成的一个集合，它具有以下两条性质：

1. 线性基中任意选择一些数的异或值所构成的集合，等于原序列中任意选择一些数的异或值所构成的集合。

2. 线性基是满足上述条件的最小集合。

3. 原序列中任何数，都可以由线性基中一些数异或起来得到（由性质1直接得出）

4. 线性基中不存在一组数，使得它们的异或值为0，如果存在x xor y xor z=0则等价于x xor y =z使得异或集合变，违背了性质2）

5. 线性基中不存在两组取值集合，使得它们的异或和相等（不然你把这两个集合异或在一起就会得到异或和为0的集合）

6. 线性基中的数最高位数字1不重复

7. 线性基个数小于等于原数个数

模板

struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=60;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
    void rebuild(){
        nums.clear();
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<i;j++){
                if(d[i]>>j&1)d[i]^=d[j];
            }
            if(d[i])nums.push_back(d[i]);
        }
    }
    int kth(int k,int n){
        if(nums.size()<n){
            if(k==1)return 0;
            k--;
        }
        if(k>=(1ll<<nums.size()))return -1;
        int res=0;
        for(int i=SIZE-1;i>=0;i--){
            if(k>>i&1)res^=nums[i];
        }
        return res;
    }
    int find_rank(int x){
        int rk=0,tp=1,y=x;
        for(int i=0;i<SIZE;i++){
            if(!(y>>i&1))continue;
            if(d[i])y^=d[i];
            else return -1;
        }
        for(int i=0;i<SIZE;i++){
            if(d[i]){
                if(x>>i&1)rk+=tp;
                tp<<=1;
            }
        }
        return rk;
    }
    LinearBasis operator|(const LinearBasis &rhs)const{
        LinearBasis res=*this;
        for(int i=0;i<SIZE;i++){
            if(rhs.d[i])res.insert(rhs.d[i]);
        }
        return res;
    }
    LinearBasis operator&(const LinearBasis &rhs)const{
        LinearBasis res;
        auto d=*this,all=*this;
        for(int i=0;i<SIZE;i++){
            if(!rhs.d[i])continue;
            int k=0,j;
            int v=rhs.d[i];
            for(j=i;j>=0;j--){
                if(v>>j&1){
                    if(all.d[j])v^=all.d[j],k^=d.d[j];
                    else break;
                }
            }
            if(!v)res.d[i]=k;
            else all.d[j]=v,d.d[j]=k;
        }
        return res;
    }
};

贪心构造

int d[60];
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
//查询异或最大值
int query(){
    int res=0;
    for(int i=55;i>=0;i--){
        if(res>>i&1)continue;
        res^=d[i];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(x);
    }
    cout<<query()<<"\n";
}

高斯消元法构造

int d[70];
void gauss(int n){
    int k=1;
    for(int i=62;i>=0;i--){
        for(int j=k;j<=n;j++){
            if(d[j]>>i&1){
                swap(d[j],d[k]);
                break;
            }
        }
        if(!(d[k]>>i&1))continue;
        for(int j=1;j<=n;j++){
            if(j!=k&&(d[j]>>i&1))d[j]^=d[k];
        }
        if(k==n)break;
        k++;
    }
}
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
int query(){
    int res=0;
    for(int i=55;i>=0;i--){
        res^=d[i];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>d[i];
    gauss(n);
    cout<<query()<<"\n";
}

求min异或值

• 当某次数插入失败时，异或值为0
• 否则为min d[i]

求第k小异或和

• 重构线性基，使得每一位在线性基中只有当前位为1
• 求第k小直接对k二进制拆分算异或即可
• 注意：如果d[i]不为0的个数小于n，说明有插入失败，存在异或为0，询问需要减一

int d[70];
void insert(int x){
    for(int i=55;i>=0;i--){
        if(!(x>>i&1))continue;
        if(d[i])x^=d[i];
        else{
            d[i]=x;
            break;
        }
    }
}
vector<int> nums;
void rebuild(){
    for(int i=0;i<=55;i++){
        for(int j=i-1;j>=0;j--){
            if(d[i]&(1ll<<j))d[i]^=d[j];
        }
        if(d[i])nums.push_back(d[i]);
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        insert(x);
    }
    rebuild();
    int m;
    cin>>m;
    while(m--){
        int x;
        cin>>x;
        if(nums.size()<n)x--;
        if(x>=(1ll<<nums.size()))cout<<"-1\n";
        else{
            int ans=0;
            for(int i=55;i>=0;i--){
                if(x>>i&1)ans^=nums[i];
            }
            cout<<ans<<"\n";
        }
    }
}

求异或路径（最大值最小值）

• 建立dfs树，把所有的环异或值加进线性基
• 查询与$dis_n$异或的最大值（最小值）

实数线性基

const double eps=1e-6;
template <typename T>
struct Vector{
    vector<T> a;
    Vector(int n):a(n){}
    T& operator[](int i){
        return a[i];
    }
    const T& operator[](int i)const{
        return a[i];
    }
    Vector operator-(const Vector &b){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]-b[i];
        return res;
    }
    Vector operator*(const T &x){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]*x;
        return res;
    }
    Vector operator/(const T &x){
        Vector res(a.size());
        for(int i=0;i<a.size();i++)res[i]=a[i]/x;
        return res;
    }
};
template <typename T>
struct LinearBasis{
    vector<Vector<T>> d;
    int n;
    LinearBasis(){}
    LinearBasis(int n){
        init(n);
    }
    void init(int n){
        d.assign(n,Vector<T>(n));
        this->n=n;
    }
    bool insert(Vector<T> x){
        for(int i=n-1;i>=0;i--){
            if(fabs(x[i])<eps)continue;
            if(fabs(d[i][i])<eps){
                d[i]=x;
                return true;
            }
            x=x-d[i]*(x[i]/d[i][i]);
        }
        return false;
    }
};

例题

P3265 [JLOI2015] 装备购买(实数线性基)

P4570 [BJWC2011]元素（板子）

P4301 [CQOI2013] 新Nim游戏（板子）

P4151 [WC2011] 最大XOR和路径/CF845G Shortest Path Problem?（最短异或路径）

给定一个张无向图，求1到n的最小异或路径

• 随便建出一棵树，做异或前缀和，两点间的异或和即$dis_u \oplus dis_v$
• 关键：图上任意条从1到n的路径，都可以用若干个环的异或和$dis_n$异或出来

struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=60;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
    void rebuild(){
        nums.clear();
        for(int i=0;i<SIZE;i++){
            for(int j=0;j<i;j++){
                if(d[i]>>j&1)d[i]^=d[j];
            }
            if(d[i])nums.push_back(d[i]);
        }
    }
    int kth(int k,int n){
        if(nums.size()<n){
            if(k==1)return 0;
            k--;
        }
        if(k>=(1ll<<nums.size()))return -1;
        int res=0;
        for(int i=SIZE-1;i>=0;i--){
            if(k>>i&1)res^=nums[i];
        }
        return res;
    }
    LinearBasis operator|(const LinearBasis &rhs)const{
        LinearBasis res=*this;
        for(int i=0;i<SIZE;i++){
            if(rhs.d[i])res.insert(rhs.d[i]);
        }
        return res;
    }
    LinearBasis operator&(const LinearBasis &rhs)const{
        LinearBasis res;
        auto d=*this,all=*this;
        for(int i=0;i<SIZE;i++){
            if(!rhs.d[i])continue;
            int k=0,j;
            int v=rhs.d[i];
            for(j=i;j>=0;j--){
                if(v>>j&1){
                    if(all.d[j])v^=all.d[j],k^=d.d[j];
                    else break;
                }
            }
            if(!v)res.d[i]=k;
            else all.d[j]=v,d.d[j]=k;
        }
        return res;
    }
} lb;
int n,m,dis[N];
bool vis[N];
vector<PII> adj[N];
void dfs(int u,int fa){
    vis[u]=true;
    for(auto [v,w]:adj[u]){
        if(v==fa)continue;
        if(vis[v]){
            lb.insert(dis[u]^dis[v]^w);
        }
        else{
            dis[v]=dis[u]^w;
            dfs(v,u);
        }
    }
}
void solve(){ 
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    dfs(1,0);
    cout<<lb.query_max(dis[n])<<"\n";
}

CF724G Xor-matic Number of the Graph（异或路径和）

给定一个张无向图，求任意路径的异或和的总和

• 建出生成树

• 把环加入线性基B

• 同理，两点的任意路径可以表达为$dis_u \oplus dis_v \oplus B$

• 考虑按位考虑

• 如果线性基有$S$个数，那么线性基能表达的数为$2^S$

• 假设当前位为$w$,那么线性基里只要有一个数第$w$位为$1$，则有$2^{S-1}$个表达在该位为$1$,其他$2^{S-1}$个该位为$0$

  • 此时不管$dis_u,dis_v$的该位为$0$还是$1$，均有贡献，即任选两个数，贡献为$C_n^2 \cdot 2^w \cdot 2^{S-1}$

• 假设该位为$0$,因此$dis_u,dis_v$必须有一个为$1$，此时线性基能表达$2^S$个数，贡献为$cnt_0 \cdot cnt_1 \cdot 2^w \cdot 2^S$

struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=62;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
        nums.clear();
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
} lb;
vector<PII> adj[N];
bool vis[N];
int dis[N],t[N],idx;
void dfs(int u,int fa){
    vis[u]=1;
    t[++idx]=u;
    for(auto [v,w]:adj[u]){
        if(vis[v])lb.insert(dis[u]^dis[v]^w);
        else{
            dis[v]=dis[u]^w;
            dfs(v,u);
        }
    }
}
void solve(){ 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        idx=0;
        lb.init();
        dfs(i,0);
        int S=0;
        for(int j=0;j<62;j++)S+=lb.d[j]>0;
        for(int bit=0;bit<62;bit++){
            int tmp=(1ll<<bit)%mod;
            vector<int> v(2);
            for(int j=1;j<=idx;j++)v[dis[t[j]]>>bit&1]++;
            bool ok=0;
            for(int j=0;j<62;j++)if(lb.d[j]>>bit&1)ok=1;
            if(ok){
                ans+=idx*(idx-1)/2%mod*tmp%mod*((1ll<<S-1)%mod)%mod;
            }
            else{
                ans+=v[0]*v[1]%mod*tmp%mod*((1ll<<S)%mod)%mod;
            }
            ans%=mod;
        }
    }
    cout<<ans<<'\n';
}

P5556 圣剑护符（结合树链剖分）

给定一棵树

操作1：将x到y的路径所有点异或上z

操作2：询问x到y路径的点，是否存在两个子集，异或值相等

• 考虑线性基，操作2即问是否存在插入失败
• 因为$val\lt 2^{30}$，因此最多插入31次就会出现插入失败
• 对于操作1树链剖分修改
• 操作2，因为路径最长30，可以暴力

struct node{
    int l,r,tag,sum;
} t[N<<2];
int w[N],siz[N],dfn[N],seq[N],dep[N],top[N],par[N],son[N],ts;
vector<int> adj[N];
void dfs1(int u,int fa){
    par[u]=fa;
    dep[u]=dep[fa]+1;
    siz[u]=1;
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])son[u]=v;
    }
}
void dfs2(int u,int t){
    dfn[u]=++ts;
    seq[ts]=w[u];
    top[u]=t;
    if(!son[u])return;
    dfs2(son[u],t);
    for(auto v:adj[u]){
        if(v==par[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
void apply(int p,int x){
    t[p].tag^=x;
    t[p].sum^=x;
}
void pushdown(int p){
    if(t[p].tag){
        apply(p<<1,t[p].tag);
        apply(p<<1|1,t[p].tag);
        t[p].tag=0;
    }
}
void build(int p,int l,int r){
    t[p]={l,r,0,0};
    if(l==r){
        t[p].sum=seq[l];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x){
    if(l<=t[p].l&&r>=t[p].r){
        apply(p,x);
        return;
    }
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)modify(p<<1,l,r,x);
    if(r>mid)modify(p<<1|1,l,r,x);
}
void modify_path(int u,int v,int k){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,dfn[top[u]],dfn[u],k);
        u=par[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    modify(1,dfn[v],dfn[u],k);
}
int query(int p,int x){
    if(t[p].l==t[p].r)return t[p].sum;
    pushdown(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)return query(p<<1,x);
    return query(p<<1|1,x);
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=par[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int dist(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=62;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
        nums.clear();
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
} lb;
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(q--){
        string op;
        int x,y,z;
        cin>>op;
        if(op=="Update"){
            cin>>x>>y>>z;
            modify_path(x,y,z);
            continue;
        }
        cin>>x>>y;
        int dis=dist(x,y);
        if(dis>31){
            cout<<"YES\n";
            continue;
        }
        lb.init();
        if(dep[x]<dep[y])swap(x,y);
        while(dep[x]!=dep[y]){
            lb.insert(query(1,dfn[x]));
            x=par[x];
        }
        while(x!=y){
            lb.insert(query(1,dfn[x]));
            lb.insert(query(1,dfn[y]));
            x=par[x];
            y=par[y];
        }
        lb.insert(query(1,dfn[x]));
        cout<<(lb.fail?"YES\n":"NO\n");
    }
}

CF895C Square Subsets(思维+状压)

题意：

有多少个非空子集乘积为完全平方数，$1 \leq a_i \leq 70$

• 1-70的质因数只有19个，可以状压
• 对于每个数值都有一个状态值，题目转变成选出一些状态值异或和为0
• 假设插入失败次数为$x$,答案即为$2^x-1$，需要减去空集
• 可以状压dp，但是状压dp的复杂度为$70 \cdot 2^{19}$,而线性基的复杂度为$70 \cdot 19$

int prime[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int cnt[70],state[70];
int qpow(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    for(int i=1;i<=70;i++){
        int x=i;
        for(int j=0;j<19;j++){
            while(x%prime[j]==0){
                state[i]^=1<<j;
                x/=prime[j];
            }
        }
        for(int j=1;j<=cnt[i];j++)lb.insert(state[i]);
    }
    int ans=1;
    for(int i=1;i<=lb.fail;i++)ans=ans*2%mod;
    cout<<ans-1<<"\n";
}

E - Magical Permutation（思维构造）

给n个数$S_1,S_2,S_3,....$，构造一个最大的x，和一个长度为$2^x$的排列

满足相邻两个数的异或值都出现在集合$S$中

思路：

• 找出排列中的0假设坐标为$i$
• 那么$c_{i+1} \oplus c_{i}=x_1,c_{i+2} \oplus c_{i+1}=x_2,c_{i+3} \oplus c_{i+2}=x_3$
• $x_1,x_2,x_3,...$在集合$S$中
• $c_{i+1}=x_1,c_{i+2}=x_1 \oplus x_2,c_{i+2}=x_1 \oplus x_2 \oplus x_3$以此类推，左边同理。因此排列中的所有数都可以被集合内部若干个数异或得到
• 对应线性基插满的情况，因此假设我们找到了对应的线性基组成的数，考虑如何构造
• 假设线性基有$x$个数，那么可以组成的异或值为$2^x$，每个数选与不选，用状压表示，即相邻二进制位只有一个$1$是相同的，这就是格雷码
• 或者另一种神秘构造(见代码1)，实际好像也是格雷码？

void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    lb.init();
    int x=1;
    vector<int> res;
    for(int i=0,j=1;i<=20;i++){
        while(j<=n&&a[j]<(1<<i)){
            lb.insert(a[j++]);
        }
        if(lb.tmp.size()==i)x=i,res=lb.tmp;
    }
    vector<int> ans(1<<x);
    int idx=0;
    auto dfs=[&](auto dfs,int dep){
        if(dep==-1)return;
        dfs(dfs,dep-1);
        ans[++idx]=res[dep];
        dfs(dfs,dep-1);
    };
    dfs(dfs,x-1);
    cout<<x<<"\n";
    for(int i=0;i<(1<<x);i++){
        if(i)ans[i]^=ans[i-1];
        cout<<ans[i]<<" \n"[i==(1<<x)-1];
    }
}

标准格雷码构造

void solve(){ 
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    lb.init();
    int x=1;
    vector<int> res;
    for(int i=0,j=1;i<=20;i++){
        while(j<=n&&a[j]<(1<<i)){
            lb.insert(a[j++]);
        }
        if(lb.tmp.size()==i)x=i,res=lb.tmp;
    }
    vector<int> ans(1<<x);
    for(int i=0;i<(1<<x);i++){
        for(int j=0;j<x;j++){
            if(i>>j&1)ans[i]^=res[j];
        }
    }
    cout<<x<<"\n";
    for(int i=0;i<(1<<x);i++){
        cout<<ans[i^(i>>1)]<<" \n"[i==(1<<x)-1];
    }
}

P3292 [SCOI2016] 幸运数字（LCA）

题意：

给一棵树，每个点有一个权值，每次询问给出x和y，求路径上的异或最大值

思路： 暴力lca，$O(nlog^3n)$

int par[N][16],dep[N],w[N];
vector<int> adj[N];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    par[u][0]=fa;
    for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto v:adj[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=par[x][__lg(dep[x]-dep[y])];
    if(x==y)return x;
    for(int i=__lg(dep[x]);i>=0;i--){
        if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i];
    }
    return par[x][0];
}
int jump(int x,int y){
    LinearBasis res;
    int l=lca(x,y);
    int tmp=dep[x]-dep[l];
    for(int i=__lg(tmp)+1;i>=0;i--){
        if(tmp>>i&1){
            res=res|lb[x][i];
            x=par[x][i];
        }
    }
    tmp=dep[y]-dep[l];
    for(int i=__lg(tmp)+1;i>=0;i--){
        if(tmp>>i&1){
            res=res|lb[y][i];
            y=par[y][i];
        }
    }
    res.insert(w[l]);
    return res.query_max();
}
void solve(){ 
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)lb[i][0].insert(w[i]);
    for(int j=1;j<=__lg(n);j++){
        for(int i=1;i<=n;i++){
            lb[i][j]=lb[i][j-1]|lb[par[i][j-1]][j-1];
        }
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<jump(x,y)<<'\n';
    }
}

P4839 P 哥的桶（单点修改，区间异或最大值查询，线段树写法）

题意：

单点修改，区间异或最大值

思路：

线性基，暴力合并$O(nlog^3n)$

struct Node{
    int l,r;
    LinearBasis lb;
} t[N<<2];
void build(int p,int l,int r){
    t[p]={l,r};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void modify(int p,int x,int val){
    if(t[p].l==t[p].r){
        t[p].lb.insert(val);
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,val);
    else modify(p<<1|1,x,val);
    t[p].lb=t[p<<1].lb|t[p<<1|1].lb;
}
LinearBasis query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].lb;
    int mid=t[p].l+t[p].r>>1;
    LinearBasis res;
    if(l<=mid)res=res|query(p<<1,l,r);
    if(r>mid)res=res|query(p<<1|1,l,r);
    return res;
}
void solve(){ 
    int n,m;
    cin>>m>>n;
    build(1,1,n);
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            modify(1,l,r);
        }
        else{
            auto res=query(1,l,r);
            cout<<res.query_max()<<"\n";
        }
    }
}

单点插入，区间异或最大值查询，猫树分治写法

另一种做法：

• 利用猫树分治的思想，对于线段树左儿子维护后缀线性基，右儿子维护前缀线性基
• 那么插入的时候，对于每一个经过的节点都插入，单次插入复杂度为$\log n \log V$
• 查询的时候找到完全包含查询区间的节点，从mid裂开，即合并该节点的左儿子和右儿子，只需合并一次，总复杂度为$\log n + \log^2V$
• 少一个log，速度大大提升

struct PrefixLinearBasis{
    vector<int> d,pos;
    static constexpr int SIZE=35;
    PrefixLinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        pos.assign(SIZE,-1);
    }
    bool insert(int x,int p,int lim){
        for(int i=SIZE-1;~i;i--){
            if(!(x>>i&1))continue;
            if(d[i]){
                if(abs(p-lim)<abs(pos[i]-lim)){
                    swap(pos[i],p);
                    swap(d[i],x);
                }
                x^=d[i];
            }
            else{
                d[i]=x;
                pos[i]=p;
                return true;
            }
        }
        return false;
    }
    int query_max(int l=0){
        int ans=0;
        for(int i=SIZE-1;~i;i--){
            if(pos[i]>=l)ans=max(ans,ans^d[i]);
        }
        return ans;
    }
};
struct Node{
    int l,r;
    PrefixLinearBasis lb;
} t[N<<2];
void build(int p,int l,int r){
    t[p]={l,r};
    if(l==r)return;
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void modify(int p,int x,int val){
    if(p>1){
        if(p&1)t[p].lb.insert(val,x,-INF);
        else t[p].lb.insert(val,x,INF);
    }
    if(t[p].l==t[p].r)return;
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,val);
    else modify(p<<1|1,x,val);
}
int query(int p,int l,int r,int val=0){
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid&&r>=mid){
        PrefixLinearBasis lb;
        for(int i=0;i<lb.SIZE;i++){
            if(t[p<<1].lb.pos[i]>=l&&t[p<<1].lb.pos[i]<=r)lb.insert(t[p<<1].lb.d[i],0,0);
            if(t[p<<1|1].lb.pos[i]>=l&&t[p<<1|1].lb.pos[i]<=r)lb.insert(t[p<<1|1].lb.d[i],0,0);
        }
        return lb.query_max(val);
    }
    if(l<=mid)return query(p<<1,l,r,val);
    return query(p<<1|1,l,r,val);
}

CF1100F（前缀线性基）

• 给一个序列，q次询问，每次询问区间最大值
• 使用线段树会超时且爆空间，不带修，使用前缀线性基
• 前缀线性基维护多一个pos数组代表插入的时刻，对于每个右端点r对应的版本而言，肯定是希望每个数的pos越大越好
• 因此如果当前pos小于插入的pos，直接替换，然后替换出来的值代替旧值继续插入

struct PrefixLinearBasis{
    vector<int> d,pos;
    static constexpr int SIZE=20;
    PrefixLinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        pos.assign(SIZE,-1);
    }
    bool insert(int x,int p){
        for(int i=SIZE-1;~i;i--){
            if(!(x>>i&1))continue;
            if(d[i]){
                if(pos[i]<p){
                    swap(pos[i],p);
                    swap(d[i],x);
                }
                x^=d[i];
            }
            else{
                d[i]=x;
                pos[i]=p;
                return true;
            }
        }
        return false;
    }
    int query_max(int l=0){
        int ans=0;
        for(int i=SIZE-1;~i;i--){
            if(pos[i]>=l)ans=max(ans,ans^d[i]);
        }
        return ans;
    }
} lb;
void solve(){ 
    int n,m;
    cin>>n;
    vector<int> w(n+1);
    vector<PrefixLinearBasis> lb(n+1);
    for(int i=1;i<=n;i++){
        cin>>w[i];
        lb[i]=lb[i-1];
        lb[i].insert(w[i],i);
    }
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<lb[r].query_max(l)<<"\n";
    }
}

P11620 [Ynoi Easy Round 2025] TEST_34/CF587E（区间线性基求法）（线段树 or 随机算法）

题意：

• 操作一：$[l,r]$区间每个数异或上$v$
• 操作二：查询区间异或最值

思路：

• 差分异或数组，$b_i=a_i \oplus a_{i-1}$
• 变成单点修改，改变$b_l$和$b_{r+1}$即可
• $a_l,a_{l+1},a_{l+2},...,a_r$的线性基等价于$a_l,b_{l+1},....,b_r$的线性基
• 原数组$a_i$的值用树状数组维护
• 方法一：线段树，和P4839相同

int a[N];
struct Node{
    int l,r;
    LinearBasis lb;
} t[N<<2];
void build(int p,int l,int r){
    t[p]={l,r};
    if(l==r){
        t[p].lb.insert(a[l]);
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p].lb=t[p<<1].lb|t[p<<1|1].lb;
}
void modify(int p,int x,int val){
    if(t[p].l==t[p].r){
        t[p].lb.init();
        t[p].lb.insert(val);
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)modify(p<<1,x,val);
    else modify(p<<1|1,x,val);
    t[p].lb=t[p<<1].lb|t[p<<1|1].lb;
}
LinearBasis query(int p,int l,int r){
    if(l<=t[p].l&&r>=t[p].r)return t[p].lb;
    int mid=t[p].l+t[p].r>>1;
    LinearBasis res;
    if(l<=mid)res=res|query(p<<1,l,r);
    if(r>mid)res=res|query(p<<1|1,l,r);
    return res;
}
template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_=0){
        init(n,identity);
    }
    void init(int n_,T identity_=0){
        n=n_;
        c.assign(n,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
Fenwick<int,decltype([](const int &a,const int &b){return a^b;})> fw;
void solve(){
    int n,m;
    cin>>n>>m;
    fw.init(n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--)a[i]^=a[i-1],fw.add(i,a[i]);
    build(1,1,n);
    while(m--){
        int op,l,r,v;
        cin>>op>>l>>r>>v;
        if(op==1){
            fw.add(l,v);
            a[l]^=v;
            modify(1,l,a[l]);
            if(r<n){
                fw.add(r+1,v);
                a[r+1]^=v;
                modify(1,r+1,a[r+1]);
            }
        }
        else{
            int x=fw.query(l);
            if(l==r){
                cout<<max(v,x^v)<<"\n";
                continue;
            }
            auto res=query(1,l+1,r);
            res.insert(x);
            cout<<res.query_max(v)<<"\n";
        }
    }
}

查询区间异或最值，随机法

方法二：

• zak随机大法，来自zky在2025WC的讲解
• 具体地，维护长度等于数组$a$的$S$个序列，每个序列第$i$个位置，有$\frac{1}{2}$的概率为$a_i$，$\frac{1}{2}$为$0$
• 每次查询将$S$个序列的区间$[l,r]$异或和加入线性基，可以证明这在极大概率上等价于原区间的线性基
• 具体证明见：https://molmin.github.io/image/2025/01/18/qian-tan-fei-que-ding-xing-suan-fa-zhou-kang-yang.pdf

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dis(0,1);
struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=__lg(1000000000)+1;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
        nums.clear();
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
};
template<typename T,typename F>
struct Fenwick{
    int n;
    vector<T> c;
    T identity;
    F op;
    Fenwick(){}
    Fenwick(int n_,T identity_=0){
        init(n,identity);
    }
    void init(int n_,T identity_=0){
        n=n_;
        c.assign(n,identity);
        identity=identity_;
    }
    void add(int x,T v,int rev=0){
        if(rev)x=n-x+1;
        for(;x<=n;x+=x&-x)c[x]=op(c[x],v);
    }
    T query(int x,int rev=0){
        if(rev)x=n-x+1;
        T res=identity;
        for(;x;x&=x-1)res=op(res,c[x]);
        return res;
    }
};
const int S=__lg(50000)+__lg(1000000000)+1;
Fenwick<int,decltype([](const int &a,const int &b){return a^b;})> fw[S],ori;
bool have[S][N];
int a[N];
int n,m;
void solve(){ 
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    ori.init(n+1);
    for(int i=n;i>=1;i--)a[i]^=a[i-1],ori.add(i,a[i]);
    for(int i=0;i<S;i++){
        fw[i].init(n+1);
        for(int j=1;j<=n;j++){
            have[i][j]=dis(rng);
            if(have[i][j])fw[i].add(j,a[j]);
        }
    }
    while(m--){
        int op,l,r,v;
        cin>>op>>l>>r>>v;
        if(op==1){
            ori.add(l,v);
            a[l]^=v;
            for(int i=0;i<S;i++){
                if(have[i][l])fw[i].add(l,v);
            }
            if(r<n){
                ori.add(r+1,v);
                a[r+1]^=v;
                for(int i=0;i<S;i++){
                    if(have[i][r+1])fw[i].add(r+1,v);
                }
            }
            continue;
        }
        int x=ori.query(l);
        if(l==r){
            cout<<max(v,x^v)<<"\n";
            continue;
        }
        LinearBasis lb;
        lb.insert(x);
        for(int i=0;i<S;i++)lb.insert(fw[i].query(r)^fw[i].query(l));
        cout<<lb.query_max(v)<<"\n";
    }
}

CF959(板子)

题意：

一个序列，$q$次询问，每次询问l x，在前缀$l$中有多少种选取方法使得异或值为$x$

思路：

每个前缀维护一个线性基

查询时，首先看是否能组成$x$，如果不能则为$0$，否则为$2^{fail}$，插入失败的数可以选与不选

void solve(){ 
    int n,m;
    cin>>n>>m;
    vector<LinearBasis> lb(n+1);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        lb[i]=lb[i-1];
        lb[i].insert(x);
    }
    while(m--){
        int l,v;
        cin>>l>>v;
        if(lb[l].find(v))cout<<qpow(2,lb[l].fail)<<"\n";
        else cout<<0<<"\n";
    }
}

P4869 albus就是要第一个出场(构造+查询排名)

题意：

给定一个集合，将所有子集异或和列举出来排序，查询$x$第一次出现的位置

思路：

• 首先如果不去重，直接查询即可
• 可以发现每个数出现的次数相同，等于插入失败的次数，因此答案为$rk\cdot 2^{fail}+1$

struct LinearBasis{
    vector<int> d;
    int fail,mxb;
    static constexpr int SIZE=60;
    vector<int> nums;
    LinearBasis(){
        init();
    }
    void init(){
        d.assign(SIZE,0);
        fail=mxb=0;
        nums.clear();
    }
    bool insert(int x){
        for(int i=SIZE-1;i>=0;i--){
            if(!(x>>i&1))continue;
            mxb=max(mxb,i);
            if(d[i])x^=d[i];
            else{
                d[i]=x;
                return true;
            }
        }
        fail++;
        return false;
    }
    int query_max(int res=0){
        for(int i=SIZE-1;i>=0;i--){
            res=max(res,res^d[i]);
        }
        return res;
    }
    int query_min(int res=0){
        if(!res)return fail?0:*min_element(d.begin(),d.begin()+mxb+1);
        for(int i=SIZE-1;i>=0;i--){
            res=min(res,res^d[i]);
        }
        return res;
    }
    int find_rank(int x){
        int rk=0,tp=1,y=x;
        // for(int i=0;i<SIZE;i++){
        //     if(!(y>>i&1))continue;
        //     if(d[i])y^=d[i];
        //     else return -1;
        // }
        for(int i=0;i<SIZE;i++){
            if(d[i]){
                if(x>>i&1)rk+=tp;
                tp<<=1;
            }
        }
        return rk;
    }
} lb;
void solve(){ 
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        lb.insert(x);   
    }
    int x;
    cin>>x;
    const int mod=10086;
    int rk=lb.find_rank(x);
    rk=rk%mod*qpow(2,lb.fail,mod)%mod;
    cout<<(rk+1)%mod<<"\n";
}

2024CCPC网络赛J/(https://codeforces.com/gym/105336/)（线性基贪心）

题意：

两个数组$A,B$，定义$f(A)= \bigoplus_{i=1}^nA_i$，可以进行若干次操作交换$A_i$和$B_i$，最小化$\max(f(A),f(B))$

• 首先计算出两个数组异或和$x,y$
• 交换两个数相当于同时异或$A_i \oplus B_i$
• 把所有$A_i \oplus B_i$插入线性基考虑
• 按位贪心

int dfs(int i,int x,int y){
    if(i==-1)return max(x,y);
    int l=x>>i&1,r=y>>i&1;
    if(!lb.d[i]||(l==0&&r==0))return dfs(i-1,x,y);
    if(l==1&&r==1)return dfs(i-1,x^lb.d[i],y^lb.d[i]);
    if((l==1&&r==0&&x>y)||(l==0&&r==1&&x<y))return dfs(i-1,x^lb.d[i],y^lb.d[i]);
    return dfs(i-1,x,y);
}
void solve(){ 
    lb.init();
    int n;
    cin>>n;
    int x=0,y=0;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],x^=a[i];
    for(int i=1;i<=n;i++)cin>>b[i],y^=b[i],lb.insert(a[i]^b[i]);
    cout<<dfs(31,x,y)<<"\n";
}