奶油异或

题意

让你找一个连续区间异或和最大，如果有多种方案，输出右端点最小的，如果还有多种方案，输出最短的

分析

关于异或，有这样一个性质 ，如果用 表示 的异或前缀和，那么有 ，就是说这样可以很轻松的求的一个区间的异或和
所以在 字典树上，我们可以插入 的异或前缀和，结尾的时候标记一下这是谁的前缀和，那么查询就是和这个专题的上一道题一样
需要注意的是，如何得到“右端点最小，最短的方案呢”
显然第一个严格大于上一次的答案保证了右段点最小，因为字典树的性质，相同的数在叶子节点上的信息又是最靠右的，那么这个有保证了最短，所以不需要可以做什么其他的操作来得到答案

Code

#include <cstdio>

const int maxn = 1e5 + 10;
int n, id, ans(-1), l, r, temp;
int son[maxn * 32][2], end[maxn * 32];

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

inline void Insert(int temp, int x)
{
    int p(0);
    for (int i = 20; ~i; --i) {
        int sta = (temp >> i) & 1;
        if (!son[p][sta]) son[p][sta] = ++id;
        p = son[p][sta];
    }
    end[p] = x;
}

inline void find(int x)
{
    int p(0), res(0);
    for (int i = 20; ~i; --i) {
        int sta = (temp >> i) & 1;
        if (son[p][sta ^ 1]) p = son[p][sta ^ 1], res |= 1 << i;
        else if (son[p][sta]) p = son[p][sta];
        else break;
    }
    if (res > ans) ans = res, l = end[p], r = x;
}

int main()
{
    n = __read();
    Insert(0, 0);
    for (int i = 1; i <= n; ++i) {
        temp ^= __read();
        find(i);
        Insert(temp, i);
    }
    printf ("%d %d %d\n", ans, l + 1, r);
}