还以为是什么非常高大上的东西花了1h不到就学好了

线性基

线性基可以在\(O(nlogx)\)的时间内计算出\(n\)个数的最大异或和（不需要相邻）。

上述中\(x\)表示的最大的数。

如何实现

定义\(p[i]\)表示在二进制下从最高位开始第一个出现\(1\)的数。

当前我们将一个数插入线性基中。

如果\(x\)的最高位的\(1\)还没有被插入过，那么就在这一位上插入\(x\)。

如果当前这一位被插入过，那么就异或上这一位上的数。

查询操作：从最高位上开始贪心。

如果异或这一位上的数可以让答案更大，那么就异或，否则就异或。

贪心验证

因为我们从高位往低位贪心，所以不需要考虑低位上的数会让高位上的数变小的情况。

介于我们在插入的时候都是无法匹配的时候，异或上这一位上的数，那么就保证了我们的这个数能够达到自己能用的最大贡献。

代码

#include 
    
     using namespace std;const int BIT = 63;const int N = 52;typedef long long ll;ll a[N], p[BIT + 2];int n; void ins(ll x) {    for (int i = BIT; ~i; i --) {        if ((x >> i) == 0) continue;         if (!p[i]) { p[i] = x; break; }        x ^= p[i];    }}int main() {    cin >> n;    for (int i = 1; i <= n; i ++) cin >> a[i];    for (int i = 1; i <= n; i ++) ins(a[i]);    for (int i = 0; i <= BIT; i ++) cout << i << " " << p[i] << endl; cout << endl;    ll ans = 0;    for (int i = BIT; ~i; i --)         if ((ans ^ p[i]) > ans) ans ^= p[i];    cout << ans << endl;    return 0;}