奶牛异或（位运算、Trie）

题意

给定(n)个整数，找出一个连续的非空子序列，使得子序列中元素的异或和最大。
如果存在多个这样的序列，那么选择序列末端整数对应的编号更小的那个序列。
如果仍然存在多个可选的序列，那么选择长度最短的那个序列。

数据范围

(1 leq n leq 10^5)
序列中每个整数的取值范围是([0, 2^{21} - 1])

思路

我们可以将这个问题拆成几个子问题来考虑。

1. 如果给定若干数，两两异或，问异或的最大值是多少。这个问题可以建立Trie，然后遍历每个数，在Trie上贪心的找到与这个数异或最大的数
2. 求区间异或和。 求前缀异或和(s[i])，区间([l, r])的异或和为(s[r])异或(s[l - 1])

现在我们再看这个题，我们可以先求前缀异或和，然后枚举每个数作为右端点
在Trie中，看看前面的数哪个与它异或值最大。
这里需要注意的是，需要一边枚举，一边插入数据，因为看的是其左边的数。
用一个数组记录Trie每个结尾点对应的序列编号，这样在插入数据的过程中，如果两个数相同，那么后面的会将前面的覆盖掉，这样保证了长度最短。

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 21 * N;

int n;
int a[N], son[M][2], id[M], idx;

void insert(int x, int k)
{
    int p = 0;
    for(int i = 20; i >= 0; i --) {
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
    id[p] = k;
}

int search(int x)
{
    int p = 0;
    for(int i = 20; i >= 0; i --) {
        int s = x >> i & 1;
        if(son[p][!s]) p = son[p][!s];
        else p = son[p][s];
    }
    return id[p];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        int x;
        scanf("%d", &x);
        a[i] = x ^ a[i - 1];
    }
    int res = -1;
    int l, r;
    insert(a[0], 0);
    for(int i = 1; i <= n; i ++) {
        int k = search(a[i]);
        int t = a[i] ^ a[k];
        if(t > res) res = t, l = k + 1, r = i;
        insert(a[i], i);
    }
    printf("%d %d %d
", res, l, r);
    return 0;
}