线性基

准确的来说，线性基这个概念可以扩展到更大的线性空间中，但本文只包括了异或线性基。

线性基

定义

对于一个序列来说，一个满足如下条件的集合称作其线性基（不唯一）：

1. 线性基中任意选择一些数（可以不选）的异或值所构成的集合，与原序列中任意选择一些数的异或值所构成的集合相同。
2. 该集合的元素个数最少。

比如对于序列 $\{1,4,5,7\}$ 来说，其一个线性基就是 $\{1,3,4\}$。

性质

1. 线性基中不存在取值集合，使得异或和为 $0$。
   否则可以删去一个数，仍然可以表达出一样的集合。
2. 线性基中不存在任意两组取值集合，使得异或和相等。
   否则就能得到异或和为 $0$ 的取值集合。
3. 若线性基的大小为 $S$，能异或出的数（包括不选得到 $0$）个数为 $2^S$。
   由性质 2 可知任意异或都不重复，故个数为 $2^S$。

建立线性基

贪心算法

假设当前插入的数是 $x$，我们的线性基为 $b_0,b_1,\ldots,b_k$，初始都为 $0$。

从高到低扫，如果 $x$ 第 $p$ 位是 $1$，如果 $b_p=0$，令 $b_p\leftarrow x$，结束扫描；否则令 $x\leftarrow x\oplus b_p$，继续扫描。（$\oplus$ 表示异或运算，下同）

代码：

int b[31]; // 1e9范围内只要30就够了，根据题目调整
void ins(int x){
    for(int i=30;i>=0;i--){  // 从高往低
        if((x>>i)&1){ // 有 i 位
            if(!b[i]){b[i]=x;break;}
            x^=b[i];
        }
    }
}

单次插入复杂度 $O(\log V)$（$n$ 为序列长度，$V$ 为值域，下同）

正确性

可以发现这样构建出的线性基满足 $b_i$ 最高位为 $i$。

如果一个数 $x$ 没能被插入线性基，最后算法执行完之后一定变成了 $0$，这就说明 $x$ 已经能被当前线性基中的某些数表示出来了，自然没有必要插入。

如果 $x$ 被插入了线性基，可以发现当前线性基是无法异或得到 $x$ 的（考虑贪心消去每一位的过程），所以就需要插入 $x$。

尽管我们插入的是 $x$ 和当前线性基中某些数异或后的结果，但是依然正确，因为只要线性基不能表示出 $x$，插入 $x$ 和插入 $x$ 和线性基中任意元素异或后的结果是等价的，我们这么处理这是为了维护 $b_i$ 最高位为 $i$ 的性质，方便判断是否能异或出 $x$。

经典问题

接下来介绍一些线性基的一些经典问题。

求最大值

• P3812 【模板】线性基

给定一个序列，求其中一些元素异或得到的最大值。
升级版：给定一个序列和 $v$，求 $v$ 异或其中一些元素得到的最大值。（上面就是 $v=0$ 的特例）

解法：
先对原序列构建线性基，然后从高往低扫描，如果异或上当前的线性基变大了就异或上，最后得到的就是答案。
代码：

int b[31];
int query_max(int v=0){
    for(int i=30;i>=0;i--){
        if((v^b[i])>v)v^=b[i];
    }
    return v;
}

正确性说明：
考虑贪心，上述过程其实等价于如果 $v$ 第 $i$ 位是 $0$ 则异或 $b_i$，那当前这一位贪心的设为 $1$ 不会影响后面，所以算法是正确的。

求最小值

可以不选

这时候显然有一个初始值 $v$。

同求最大值，只需要换成小于号即可。

int b[31];
int query_min(int v){
    for(int i=30;i>=0;i--){
        if((v^b[i])<v)v^=b[i];
    }
    return v;
}

必须选某些元素

跑一遍上面的算法，如果真的一个元素都没有选那么需要额外判断，如果原序列能表示出0（也就是存在元素没有成功加入线性基）就直接返回，否则就只能异或上线性基里面的最小值。

int b[31];
int query_min_nonempty(int v=0){
    bool flag = 0;
    for(int i=30;i>=0;i--){
        if((v^b[i])<v)flag=1,v^=b[i];
    }
    if(!flag && tot!=n){ // 一个都没有选，且不能表示出0
        for(int i=0;i<=30;i++)if(b[i])return v^b[i]; // 异或最小值
    }
    return v;
}

求第 k 小

• LOJ#114. k 大异或和

给定一个序列，求其一个非空子集异或出的结果中，第 $k$ 小是多少。

线性基中一个元素异或上非自己的任意元素，得到的依然是一个线性基。

为了求出第 $k$ 小，我们要重构我们的线性基，使其满足：对于所有 $i$，要么 $b_i=0$，否则仅有 $b_i$ 第 $i$ 位上是 $1$。

从低到高，把 $b_i$ 的小于 $i$ 的是 $1$ 的位都异或上 $b_j$ 即可。

因为一定要选，特判处理 $0$ 的问题。如果线性基内元素比 $n$ 少，说明能异或得到 $0$，那么就将 $k$ 减一。（因为 $0$ 也算在线性基异或出的 $2^S$ 个元素中）

此时要求 $k<2^S$，注意不能取等，因为我们已经去掉 $0$ 了。

然后再把 $k$ 转换成二进制，如果 $k$ 第 $i$ 位上是 $1$，答案异或上线性基从小到大第 $i$ 个元素（注意不是 $b_i$）

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

ll b[51];
int pos[51];
void ins(ll x){
    for(int i=50;i>=0;i--){
        if((x>>i)&1){
            if(!b[i]){b[i]=x;break;}
            x^=b[i];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n;cin>>n;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;ins(x);
    }

    int now = 0;
    for(int i=0;i<=50;i++){
        if(!b[i])continue;
        for(int j=i-1;j>=0;j--){
            if((b[i]>>j)&1)b[i]^=b[j];
        }
        pos[now++]=i;
    }

    int m;cin>>m;
    while(m--){
        ll k;cin>>k;
        if(now != n)--k;

        if(k>=(1ll<<now)){cout << -1 << '\n';continue;}
        
        ll ans = 0;
        for(int i=0;i<=50;i++){
            if((k>>i)&1)ans^=b[pos[i]];
        }
        cout << ans << '\n';
    }
    return 0;
}

正确性说明：
把线性基中满足 $b_i\ne 0$ 的 $i$ 称作关键位，设有 $S$ 个这样的关键位。
下证：原序列异或第 $k$ 小 $val$ 满足：把 $val$ 的关键位提取出来，组合起来就是 $k$。

我们可以发现，关键位上 $0/1$ 是可以随意控制的，也就是说，我们可以表示出 $2^S$ 个数，而根据性质 3，线性基总共只能表示出 $2^S$ 个数，所以异或出的值提取出关键位两两不同。

而且，对于非关键位来说，它的控制完全依赖于前面的位。（因为 $b_i$ 最高位是 $i$，后面的不会影响非关键位）
那么前面的位确定好大小之后，这些非关键位是完全相同的，所以在排序的时候不需要考虑非关键位的影响。

而经过我们处理的线性基，保证了关键位已经不会互相干扰，因此异或之后得到的就是答案。

求排名

• P4869 albus就是要第一个出场

给定一个序列，求其所有子集（包括空集）异或出的结果中，比 $x$ 小的个数加一。

既然我们已经会求第 $k$ 小，如果没有重复，直接二分就可以额外花一个 $\log$ 代价轻松解决这个问题。

假设有 $n$ 个数，线性基大小为 $S$，可以证明：线性基异或出的 $2^S$ 种数中，每一个元素都出现了 $2^{n-S}$ 次。

证明：

我们知道有 $n-S$ 个元素插入线性基失败了。这就说明线性基中有一些元素异或出来能得到它们。那么枚举这 $n-S$ 个元素是否选择，然后先把他们的贡献消除掉，再取任意数即可。所以每个数都出现了 $2^{n-S}$ 次。

那么对于直接输出没有重复情况下求出比它小的个数，乘上 $2^{n-S}$ 再加一就是答案了。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD = 10086;

int b[31], pos[31];

void ins(int x){
    for(int i=30;i>=0;i--){ 
        if((x>>i)&1){ 
            if(!b[i]){b[i]=x;break;}
            x^=b[i];
        }
    }
}

int kth(int k){ // 第 k 小
    // 包括不选，那么不要管能不能表达出 0 了
    --k;
    int ans = 0;
    for(int i=0;i<=30;i++){
        if((k>>i)&1)ans^=b[pos[i]];
    }
    return ans;
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        ins(x);
    }

    int tot = 0;
    for(int i=0;i<=30;i++){
        if(!b[i])continue;
        for(int j=i-1;j>=0;j--){
            if((b[i]>>j)&1)b[i]^=b[j];
        }
        pos[tot++]=i;
    }

    int x; cin >> x;
    int l=1,r=1<<tot;
    while(l<r){
        int mid=(l+r)>>1;
        if(kth(mid)<x)l=mid+1;
        else r=mid;
    }
    
    --l;l %= MOD;
    for(int i=tot+1;i<=n;i++)l=(l<<1)%MOD;

    cout << l+1 << '\n';

    return 0;
}

线性基合并

直接暴力插入即可。复杂度 $O(\log^2 V)$。

template<typename T> struct Basis{
    T b[numeric_limits<T>::digits];
    int tot;
    Basis(){memset(b,0,sizeof b);tot=0;}
    bool ins(T x){
        for(int i=numeric_limits<T>::digits-1;i>=0;i--){
            if((x>>i)&1){ 
                if(!b[i]){b[i]=x;++tot;return 1;}
                x^=b[i];
            }
        }
        return 0;
    }
    friend Basis operator+(const Basis& lhs,const Basis& rhs){
        Basis ret = lhs;
        for(int i=0;i<numeric_limits<T>::digits;i++){
            if(rhs.b[i])ret.ins(rhs.b[i]);
        }
        return ret;
    }
};

线性基+贪心

P4570 [BJWC2011] 元素

按照 $\text{Magic}$ 排序从大到小加入线性基，只拿成功加入线性基的元素一定最优。

• 练习：P4301 [CQOI2013] 新Nim游戏

最大异或路径

P4151 [WC2011] 最大XOR和路径

给定带权无向图。找到一个 $1$ 到 $n$ 的路径，使得路径上边的异或和最大。
不难发现答案的贡献模式是 $1\to n$ 的任意一条路径加上若干个环构成。

但是找到图中所有的环是不可能的。我们只需要对原图求出生成树，然后只维护由非生成树边构成的环即可。假设生成树根是 $1$，非树边 $(u,v)$，加入环 $1\sim u \sim v \sim 1$ 即可。

为什么这些环就够了？
引理：一个环异或上一个环，得到的是若干个（可能没有）个环的集合。
那么对于任意一个环来说，对于其所有的非树边，都异或上它对应的一个环（我们的环恰包含一个非树边），则最后剩下的只有树边，显然树边不能构成环，所以剩下的是空集，即任何环都能被表示出。

找环代码：

const int N = 50000+5;
ll dis[N];
vector<pair<int,ll>> G[N];
bool vis[N];
void dfs(int u){
    vis[u]=1;
    for(auto [v,w]:G[u]){
        if(!vis[v])dis[v]=dis[u]^w,dfs(v);
        else ins(dis[v]^dis[u]^w);
    }
};

CF845G Shortest Path Problem?

同上，但是求最小值。

P3733 [HAOI2017] 八纵八横

初始给定一张连通带权无向图。
要求支持加边，删边（只会删除新加入的边），修改边权（只会修改新加入的边）操作，每次查询从 $1$ 开始回到 $1$ 的路径上边权异或最大值。

看似要维护动态图很变态。但是我们发现，有一个连通的底图是保证永远也不会破坏的。那么这张图的生成树也就是确定的。

加入/删除一条边恰与一个环有关。假设生成树上 $1\to x$ 的边权异或和是 $d_x$，那么边 $(u,v,w)$ 对应的环的异或和就是 $d_u\oplus d_v \oplus w$。
修改边直接看作删除再加入。

接下来我们只要解决带删除的线性基即可。

离线。对于每个环维护其删除时间，在插入线性基的时候如果当前的删除时间更晚就替换。（我们要保证越高位上的线性基能坚持的时间更久，这样答案才会更大）

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
const int LEN = 1001;
using bt = bitset<LEN>;

bt b[LEN];
int t[LEN];
void ins(bt x,int tx){
    for(int i=LEN-1;i>=0;i--){
        if(!x[i])continue;
        if(t[i]<tx){ // 删除时间更晚
            swap(x,b[i]);
            swap(t[i],tx);
        }
        if(!tx)break;
        x ^= b[i];
    }
}
void qmax(int td){ // 查询，时间为 td
    bt x;
    for(int i=LEN-1;i>=0;i--){
        if(td>=t[i])continue; // 已经删除了，就不管
        if(!x[i] && b[i][i])x^=b[i];
    }
    auto s = x.to_string();
    int ind=0;
    while(s[ind]=='0' && ind<s.size())++ind;
    if(ind==s.size()){
        cout<<"0\n";
    }
    else{
        for(;ind<s.size();ind++)cout<<s[ind];
        cout << '\n';
    }
}

vector<pair<int,bt>> G[N];
bt dis[N];
bool vis[N];
void dfs(int u){ // dfs找环
    vis[u]=1;
    for(auto& [v,w]:G[u]){
        if(!vis[v]){ // 树边
            dis[v] = dis[u] ^ w;
            dfs(v);
        }
        else{ // 非树边，对应一个环，永远不会被删除
            ins(dis[u] ^ dis[v] ^ w, 1e9);
        }
    }
}


bt read(){
    string s;cin>>s;
    return bt(s);
}

int deltime[N]; // 时间 i 加入的边删除时间
int sttime[N];  // 边 id 的加入时间
bt needIns[N];  // 时间 i 需要加入的值
bool need[N];   // 是否需要插入值
pair<int,int> edges[N];   // 边 id 的起点，终点


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        bt w=read();
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }

    dfs(1);

    int now = 0; // 当前边的编号
    for(int i=1;i<=q;i++){
        string op;cin>>op;
        if(op[1]=='d'){
            ++now;
            int u,v;cin>>u>>v;
            bt w=read();
            edges[now]={u,v}; // 添加 id
            need[i]=1;needIns[i]=dis[u]^dis[v]^w;
            sttime[now]=i;
        }
        if(op[1]=='h'){
            int id;cin>>id;
            bt w=read();
            deltime[sttime[id]]=i; // 先删除 id
            sttime[id]=i; // 再添加 id
            auto [u,v]=edges[id];
            need[i]=1;needIns[i]=dis[u]^dis[v]^w;
        }
        if(op[1]=='a'){
            int id;cin>>id;
            deltime[sttime[id]]=i;
        }
    }
    
    qmax(0);
    for(int i=1;i<=q;i++){
        if(need[i]){
            if(!deltime[i])deltime[i]=1e9; // 永远不会被删除
            ins(needIns[i], deltime[i]);
        }

        qmax(i);
    }

    return 0;
}

所有子集异或结果求和

【清华集训2014】玛里苟斯
给定一个有 $n$ 个元素 $a_1,a_2\ldots a_n$ 的序列 ，求 $2^n$ 个子集异或和的 $k\ (k=1,2,3,4,5)$ 次方期望。保证答案小于 $2^{63}$。

• 先考虑 $k=1$ 的情况：
  结论：设 $s = \bigvee _{i=1} ^n a_i$ （$\vee$ 表示或运算），若 $s$ 含有第 $k$ 位，总和加上 $2^k\times 2^{n-1}$，期望就加上 $2^{k-1}$。

  证明：因为 $s$ 含有第 $k$ 位，设 $a_p$ 含有第 $k$ 位。任选其他 $n-1$ 个有 $2^{n-1}$ 种方案。如果这时候第 $k$ 位已经是 $1$ 就不选 $a_p$，否则就选 $a_p$。这就说明了 $2^k$ 的贡献恰为 $2^{n-1}$。
  至于不在 $s$ 里面的，所有 $a$ 都不含，当然没有必要管这一位。

  const int N = 1e5+5;
  int n,k;
  ull a[N];
  
  void solve1(){
      ull all_or = 0;
      for(int i=1;i<=n;i++)all_or |= a[i];
      ull ans = 0; // 两倍的答案（保证是整数）
      for(int i=63;i>=0;i--){ // 从 2^63 开始枚举，因为最后还要除 2
          if((all_or>>i)&1)ans|=1ll<<i;
      }
      cout<<(ans>>1);
      if(ans&1)cout<<".5";
      cout<<'\n';
  }

  复杂度 $O(n)$。

• 再考虑 $k=2$：

  平方也可以拆贡献。假设第一次选第 $i$ 位，第二次选第 $j$ 位，贡献就是 $2^{i+j}\cdot \operatorname P(\{i,j\})$，其中 $\operatorname P(\{i,j\})$ 表示 $i,j$ 同时是 $1$ 的概率。

  这个概率怎么求？
  结论：显然 $i,j$ 都出现过，如果总是在一起出现，概率是 $1/2$，否则概率是 $1/4$。
  证明：如果总是在一起出现，概率是 $1/2$ 和上文证明一样，我们考虑证明概率是 $1/4$。
  设 $a_p$ 只有第 $i$ 位，没有第 $j$ 位，$a_q$ 有第 $j$ 位（不关心 $a_q$ 的第 $i$ 位）。可以证明一定能找出这样的 $a_p,a_q$。（可以将 $i,j$ 互换）
  那么如法炮制，其他的 $n-2$ 个元素任选，最后靠 $a_p,a_q$ 的唯一一种选法来让第 $p$ 位和第 $q$ 位都是 $1$。

  这时候的期望是 $2^{i+j-1}$（绑定），$2^{i+j-2}$（不绑定）。
  不难发现指数最小的时候只能是 $i=j=0$，此时绑定，所以答案还是 $.5$ 的形式。

  复杂度 $O(n\log^2 V)$。

  void solve2(){
      ull all_or = 0;
      for(int i=1;i<=n;i++)all_or |= a[i];
      ull ans = 0;
      for(int i=0;i<=63;i++){
          if(!((all_or>>i)&1))continue;
          for(int j=0;j<=63;j++){
              if(!((all_or>>j)&1))continue;
              int bd; // 绑定的时候为0，否则是1
              if(i==j)bd=0;
              else{
                  bd=0;
                  ull mask = (1ull<<i)|(1ull<<j);
                  for(int p=1;p<=n;p++){
                      if((a[p]&mask) && (a[p]&mask)!=mask){
                          bd=1;
                          break;
                      }
                  }
              }
  
              ans += 1ull<<(i+j-bd);
          }
      }
      cout<<(ans>>1);
      if(ans&1)cout<<".5";
      cout<<'\n';
  }

• 最后看 $k\ge 3$：

  结论：线性基大小一定不大，所以可以直接暴力枚举每个异或的值。
  证明：因为 $2^{63} \ge E[X^k] \ge \left(E[X]\right)^k$。所以 $E[X]\le \sqrt[3]{2^{63}}\approx 2^{22}$，那根据 $k=1$ 的时候结论，可以知道线性基的最大值也不会超过 $2^{23}$，所以暴力枚举是完全可以接受的。

  然后可以证明直接求 $k$ 次方虽然会爆 ull 但是不会爆 __int128。

  （可以发现这道题只有 $k\ge 3$ 的时候需要用到线性基）

  template<typename T> struct Basis{
      T b[numeric_limits<T>::digits];
      int pos[numeric_limits<T>::digits];
      int tot;
      Basis(){memset(b,0,sizeof b);tot=0;}
      void ins(T x){
          for(int i=numeric_limits<T>::digits-1;i>=0;i--){
              if((x>>i)&1){ 
                  if(!b[i]){b[i]=x;++tot;break;}
                  x^=b[i];
              }
          }
      }
      void prework(){
          int now = 0;
          for(int i=0;i<=numeric_limits<T>::digits-1;i++){
              if(!b[i])continue;
              for(int j=i-1;j>=0;j--){
                  if((b[i]>>j)&1)b[i]^=b[j];
              }
              pos[now++]=i;
          }
      }
      T kth(int _k){
          ll ans = 0;
          for(int i=0;i<tot;i++){
              if((_k>>i)&1)ans^=b[pos[i]];
          }
          return ans;
      }
      friend Basis operator+(const Basis& lhs,const Basis& rhs){
          Basis ret = lhs;
          for(int i=0;i<numeric_limits<T>::digits;i++){
              if(rhs.b[i])ret.ins(rhs.b[i]);
          }
          return ret;
      }
  };
  
  Basis<ull> b;
  void solve3(){
      for(int i=1;i<=n;i++)b.ins(a[i]);
      b.prework();
  
      __int128 ans = 0;
      for(int i=1;i<(1<<b.tot);i++){
          ull val = b.kth(i);
          __int128 now = 1;
          for(int _=0;_<k;_++)now*=val;
          ans += now;
      }   
      ans >>= (b.tot-1);
  
      cout<<ull(ans>>1);
      if(ans&1)cout<<".5";
      cout<<'\n';
  }

完整代码

序列划分成区间求异或和（前缀和转化）

CF1101G. (Zero XOR Subset)-less
给定一个序列，要求划分成尽可能多的区间，满足不存在一些区间异或和为 $0$。
$n\le 2\times 10^5$。

假设序列为 $a_1,a_2,\ldots,a_n$，前缀和 $b_i=\bigoplus_{j=1}^ia_i$。

划分为 $k$ 段，$[1,p_1],[p_1+1,p_2],\ldots,[p_{k-1}+1,n]$。
那么每一段的异或和为 $b_{p_1},b_{p_2}\oplus b_{p_1},\ldots,b_{n}\oplus b_{p_{k-1}}$。

不难发现，选出任意区间就相当于任选 $b_{p_1},b_{p_2},\ldots,b_{p_{k-1}}$ 和 $b_n$ 异或。
那么问题就转化为找到最多的 $b$ 以及 $b_n$ ，让它们线性无关。

只要 $b_n$ 不等于 $0$，那么就是 $\{b_n\}$ 的线性基元素个数（也是 $\{a_n\}$ 的线性基哦！），否则就无解。

静态区间查询线性基

CF1100F. Ivan and Burgers

给定一个序列，多次查询 $[l,r]$ 的线性基。
$n,q\le 5\times 10^5$。

显然不能线段树 $O(n\log n\log^2 V)$。

做法1（分治）

直接分治。每次处理经过中点的询问。
复杂度 $O(n\log n + q\log^2 V)$。 （离线）

做法2（猫树）

就是支持在线的分治过程。。
按照套路做 $O(n\log n\log V)$ 预处理，$O(\log^2 V)$ 单次查询。（在线）

做法3（带删除的线性基）

离线，逐一添加元素，然后把询问 $[l,r]$ 放到添加完 $r$ 之后处理。
我们对于每个线性基内的元素额外维护其下标，我们想要让高位的线性基下标尽可能大。在插入过程中，如果当前位的线性基下标更小，那么就 swap，然后查询的时候只拿下标大于等于 $l$ 的即可。

复杂度 $O((n+q)\log V)$。（离线）

用随机化解决区间修改，区间线性基询问

来自 WC2025 zky 讲义。

对于一类区间修改，区间求线性基问题来说，有如下随机化算法：

• 独立随机 $T$ 个序列，每个序列第 $i$ 个数有 $1/2$ 的概率为 $0$，$1/2$ 的概率为 $a_i$。
• 要查询区间 $[l,r]$ 的线性基，只需要查询 $T$ 个序列中 $T$ 段 $[l,r]$ 的异或和，用这 $T$ 个数求线性基，得到的线性基错误概率为 $2^{-T}$。

正确性：
没看懂。。

区间异或，区间查询

假设原序列是 $a_{[1,n]}$，差分序列是 $b_{[1,n]}$。
要求 $[l,r]$ 的线性基，只需要求 $a_l\cup b_{[l+1,r]}$ 的线性基即可。

那我们只关心 $b_{[l+1,r]}$，就是一个单点修改，区间查询的问题。

开 $T$ 个树状数组来解决即可。

P11620 [Ynoi Easy Round 2025] TEST_34
参考代码：

#include<bits/stdc++.h>
using namespace std;


const int N = 5e4+5;
const int M = 100;

int n,m;
struct BIT{
    int t[N];
    bitset<N> have;
    void modify(int i,int x){
        for(;i<=n;i+=i&-i)t[i]^=x;
    }
    int query(int i){
        int ans = 0;
        for(;i;i-=i&-i)ans^=t[i];
        return ans;
    }
    int query(int l,int r){
        return query(r)^query(l-1);
    }
}t[M];

mt19937 gen(random_device{}());


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cout<<fixed;

    cin>>n>>m;
    int last = 0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        for(int j=0;j<M;j++){
            if(j==0 || gen()%2)t[j].modify(i,x^last),t[j].have[i]=1;
        }
        last = x; 
    }

    while(m--){
        int op,l,r,v;cin>>op>>l>>r>>v;
        if(op==1){
            for(int j=0;j<M;j++){
                if(t[j].have[l])t[j].modify(l,v);
                if(r<n && t[j].have[r+1])t[j].modify(r+1,v);
            }
        }
        else{
            vector<int> basis(31);
            int x = t[0].query(l);
            for(int i=30;i>=0;i--){
                if((x>>i)&1){
                    if(!basis[i]){basis[i]=x;break;}
                    x^=basis[i];
                }
            }
            for(int j=0;j<M;j++){  
                if(l!=r){
                    x = t[j].query(l+1,r);
                    for(int i=30;i>=0;i--){
                        if((x>>i)&1){
                            if(!basis[i]){basis[i]=x;break;}
                            x^=basis[i];
                        }
                    }            
                }
            }
            int ans = v;
            for(int i=30;i>=0;i--){
                if((ans ^ basis[i] )> ans)ans^=basis[i];
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

练习：CF587E. Duff as a Queen

参考资料

• https://www.cnblogs.com/Troverld/p/14621434.html
• https://www.luogu.com.cn/article/zo12e4s5
• https://www.luogu.com.cn/article/omzqi0ql
• 浅谈非确定性算法，zhoukangyang