trie.cpp

#include <bits/stdc++.h>

using namespace std;
const int MAXB = 5e6 + 1;
struct trie{
    int links[2];
    bool finish = false;
    int cnt = 0;
} b[MAXB];

int cntV = 0;

void add(long long val){
    int v = 0;
    b[v].cnt++;
    for (int i = 40; i >= 0; i--){
        int alpha = (val >> i) & 1;
        if (b[v].links[alpha] != -1){
            v = b[v].links[alpha];
            b[v].cnt++;
        }
        else{
            cntV++;
            b[v].links[alpha] = cntV;
            v = b[v].links[alpha];
            b[v].links[0] = -1;
            b[v].links[1] = -1;
            b[v].cnt = 1;
        }
    }
    b[v].finish = true;
}

void del(long long val){
    int v = 0;
    b[v].cnt--;
    for (int i = 40; i >= 0; i--){
        int alpha = (val >> i) & 1;
        if (b[v].links[alpha] != -1){
            v = b[v].links[alpha];
            b[v].cnt--;
        }
    }
    b[v].finish = false;
}

int ffind(long long val){
    int v = 0;
    long long ans = 0;
    for (int i = 40; i >= 0; i--){
        int alpha = (val >> i) & 1;
        if (b[v].links[1 - alpha] != -1 && b[b[v].links[1 - alpha]].cnt > 0){
            ans += (1LL << i);
            v = b[v].links[1 - alpha];
        }
        else{
            v = b[v].links[alpha];
        }
    }
    return ans;
}

int main()
{
    add(0);
    add(0);
    suf[n + 1] = 0;
    for (int i = n; i >= 1; i--){
        suf[i] = suf[i + 1] ^ a[i];
        add(suf[i]);
    }
    suf[0] = 0;
    pref[0] = 0;
    for (int i = 0; i <= n; i++){
        del(suf[i])
        if (i >= 1){
            pref[i] = pref[i - 1] ^ a[i];
        }

        ans = max(ans, ffind(pref[i]));
    }


    return 0;
}