REBXOR

题面

Description

给定一个含N个元素的数组A，下标从1开始。请找出下面式子的最大值。

（A[l1]xorA[l2+1]xor…xorA[r1]）+（A[l2]xorA[l2+1]xor…xorA[r2]）

1<=l1<=r1<l2<=r2<=N

Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

Output

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

Sample Input

5

1 2 3 1 2

Sample Output

HINT

满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。

对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。

题目大意

找出两个有序数对\((L_1, R_1)\), \((L_2, R_2)\)满足\(L_1 <= R_1 < L_2 <= R_2\), 使得\(\oplus_{i = L_1}^{R_1} a_i + \oplus_{i = L_2}^{R_2}\)又最大值. 求这个最大值.

题解

我们先求出前缀异或和\(\{A_n = \oplus_{i = 1}^n a_i\}\), 则\(\oplus_{i = L}^R a_i = A_R \oplus A_{L - 1}\). 对于每一个右端点\(A_i\), 我们可以在trie上找到最大的\(A_j : j < i\)使得\(A_i \oplus A_j\)有最大值.

我们把序列反过来从右到左同样方法跑一次, 就能得到以某个位置为分界, 左边取一段异或和, 右边取一段异或和可以得到的最大值.

#include <cstdio>

#include <cctype>

#include <algorithm>

const int N = (int)4e5;

namespace Zeonfai

{

    inline int getInt()

    {

        int a = 0, sgn = 1;

        char c;

        while(! isdigit(c = getchar()))

            if(c == '-')

                sgn *= -1;

        while(isdigit(c))

            a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

struct trieTree

{

    struct node

    {

        node *suc[2];

        inline node()

        {

            suc[0] = suc[1] = NULL;

        }

    };

    node *rt;

    inline void insert(int w)

    {

        node *u = rt;

        for(int i = 30; ~ i; -- i)

        {

            int k = w >> i & 1;

            if(u->suc[k] == NULL)

                u->suc[k] = new node;

            u = u->suc[k];

        }

    }

    void Delete(node *u)

    {

        for(int i = 0; i < 2; ++ i)

            if(u->suc[i] != NULL)

                Delete(u->suc[i]);

        delete u;

    }

    inline void clear()

    {

        if(rt != NULL)

            Delete(rt);

        rt = new node();

        insert(0);

    }

    inline int query(int w)

    {

        int res = 0;

        node *u = rt;

        for(int i = 30; ~ i; -- i)

        {

            int k = w >> i & 1;

            if(u->suc[k ^ 1] == NULL)

                u = u->suc[k];

            else

                u = u->suc[k ^ 1], res |= 1 << i;

        }

        return res;

    }

}trie;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("REBXOR.in", "r", stdin);

    #endif

    using namespace Zeonfai;

    int n = getInt();

    static int a[N];

    for(int i = 0; i < n; ++ i)

        a[i] = getInt();

    static int A[N];

    A[0] = a[0];

    for(int i = 1; i < n; ++ i)

        A[i] = A[i - 1] ^ a[i];

    static int mx[N][2];

    trie.clear();

    for(int i = 0; i < n; ++ i)

        mx[i][0] = trie.query(A[i]), trie.insert(A[i]);

    for(int i = 1; i < n; ++ i)

        mx[i][0] = std::max(mx[i][0], mx[i - 1][0]);

    A[n - 1] = a[n - 1];

    for(int i = n - 2; ~ i; -- i)

        A[i] = A[i + 1] ^ a[i];

    trie.clear();

    for(int i = n - 1; ~ i; -- i)

        mx[i][1] = trie.query(A[i]), trie.insert(A[i]);

    for(int i = n - 2; ~ i; -- i)

        mx[i][1] = std::max(mx[i][1], mx[i + 1][1]);

    int ans = 0;

    for(int i = 0; i < n; ++ i)

        ans = std::max(ans, mx[i][0] + mx[i][1]);

    printf("%d\n", ans);

}

巴特西