奶牛异或

题意： 给定长度为的序列，求出连续的子序列中异或值的最大值以及子序列的首尾位置，如果有多个子序列最大值相同，则考虑最短的子序列，如果最短的仍有多个，则继续考虑末尾位置小的。
数据范围：

题解：
异或子序列的经典解决方案就是结合异或的特性，的异或值为。
当前枚举到第个前缀时，可以在树中找到与当前前缀异或得到的最大前缀。
由于考虑子序列最短，所以每个前缀值都存储当前已经枚举的最大的索引即可。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int son[N * 22][2], idx;
int id[N * 22];
void insert(int num) {
    int p = 0;
    for(int i = 21; i >= 0; --i) {
        int u = a[num] >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    id[p] = max(id[p], num);
}

int query(int x, int &f) {
    int p = 0, res = 0;
    for(int i = 21; i >= 0; --i) {
        int u = x >> i & 1;
        if(son[p][!u]) res = res * 2 + !u, p = son[p][!u];
        else res = res * 2 + u, p = son[p][u];
    }
    f = id[p];
    return res;
}

int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] ^= a[i - 1];
    int ans = a[1], fir = 1, en = 1;
    for(int i = 1; i <= n; ++i) {
        insert(i);
        int f = -1;
        int t = query(a[i], f) ^ a[i];
        if(ans < t) {ans = t, fir = f + 1, en = i;}
    }
    printf("%d %d %d\n", ans, fir, en);
    return 0;
}