Description

给定一个含 \(n\) 个元素的数组 \(A\), 下标从 \(1\) 开始. 请找出下面式子的最大值:\[ (A[l_1] \oplus A[l_1+1] \oplus \ldots \oplus A[r_1]) + (A[l_2] \oplus A[l_2+1] \oplus \ldots \oplus A[r_2]) \] 其中 \(1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \leq n\).

Input

输入数据的第一行包含一个整数 \(n\), 表示数组中的元素个数.

第二行包含 \(n\) 个整数 \(A_1, A_2, \ldots, A_n\).

Output

输出一行包含给定表达式可能的最大值.

Sample Input

5
1 2 3 1 2

Sample Output

6

Data Range

对于 100% 的数据,\(2 \leq n \leq 4 \times 10^5, 0 \leq a_i \leq 10^9\).

Explanation

建立一棵 Trie 树, 直接在上面暴力查找 \(n\) 次得到结果.

其实不是一棵, 而是 \(n\) 棵. 形态有一点像可持久化数据结构.

相当于是一个前缀和吧......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define nullptr NULL
using namespace std;
typedef long long lli;
const int maxn = 400400;

class Trie
{
public:
    struct node {
        node *ch[2];
        int size;
        #define lc ch[0]
        #define rc ch[1]
    } npool[maxn<<5], *root[maxn];
    int n, ncnt;
    node* make_node(node *ls, node *rs, int size)
    {
        node *p = &npool[++ncnt];
        p->lc = ls;
        p->rc = rs;
        p->size = size;
        return p;
    }
    node* insert(node *p, int val, int pos)
    {
        if (!pos)
            return make_node(p->lc, p->rc, p->size + 1);
        else if (val & pos)
            return make_node(p->lc, insert(p->rc, val, pos >> 1), p->size + 1);
        else
            return make_node(insert(p->lc, val, pos >> 1), p->rc, p->size + 1);
        return nullptr;
    }
    int query(node *p, node *q, int val, int pos)
    {
        #define rvpos (bool(~val&pos))
        #define vpos (bool(val&pos))
        if (!pos)
            return 0;
        if (p->ch[rvpos]->size - q->ch[rvpos]->size)
            return pos | query(p->ch[rvpos], q->ch[rvpos], val, pos >> 1);
        else
            return query(p->ch[vpos], q->ch[vpos], val, pos >> 1);
        #undef rvpos
        #undef vpos
    }
    int query(int p, int q, int val)
    {
        return query(root[p+1], root[q+1], val, 1<<29);
    }
    void init(int n, int arr[])
    {
        this->n = n;
        this->root[0] = make_node(nullptr, nullptr, 0);
        root[0]->lc = root[0]->rc = root[0];
        for (int i = 0; i <= n; i++)
            root[i+1] = insert(root[i], arr[i], 1<<29);
        return ;
    }
} tr;

int n;
int arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        arr[i] ^= arr[i - 1];
    }
    tr.init(n, arr);
    int res = 0, maxx = 0;
    for (int i = n - 1; i > 0; i--) {
        maxx = max(maxx, tr.query(n, i, arr[i]));
        res = max(res, maxx + tr.query(i, -1, arr[i]));
    }
    printf("%d\n", res);
    return 0;
}