奶牛异或（xor前缀和，01字典树）

题目：

给你个数。让你找出一个连续子序列其和最大。若方案不唯一，输出右端点最左的方案，若还不唯一，输出最短的方案。

做法：

对个数求的前缀和数组。问题转化成，在中选个数，其值最大。

做法见另一篇题解：https://blog.nowcoder.net/n/e27fd9137aed443f87b4c467a5d203d9

说明一下方案的输出思路：从左到右，统计选第个数和前个数中的某一个数值的最大值。若其值大于之前记录的方案，则该位置作为右端点更优。同时我们在上记录时保证选出来的左端点最靠右即可保证值最大的同时序列长度最短。具体就是在上插入同一个数时只记录后一个位置的。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 7;
int pre[N];
struct Trie{
    static const int N = 5e6 + 7;
    int tot, ch[N][2], tag[N];
    void insert(int x, int id){
        int now = 0;
        for (int i = 20; i >= 0; --i){
            int b = (x>>i)&1;
            if (!ch[now][b]) ch[now][b] = ++tot;
            now = ch[now][b];
        }
        tag[now] = id;
    }
    pii ask(int x){
        int now = 0, ans = 0;
        for (int i = 20; i >= 0; --i){
            int b = (x>>i)&1;
            if (ch[now][b^1]) now = ch[now][b^1], ans |= (1<<i);
            else now = ch[now][b];
        }
        return make_pair(ans, tag[now]);
    }
}trie;
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i){
        int x; cin >> x; pre[i] = pre[i-1]^x;
    }
    trie.insert(0, 1);
    int ans = -1, l, r;
    for (int i = 1; i <= n; ++i){
        pii tmp = trie.ask(pre[i]);
        if (ans < tmp.first) ans = tmp.first, l = tmp.second, r = i;
        trie.insert(pre[i], i+1);
    }
    cout << ans << ' ' << l << ' ' << r << endl; 
    return 0;
}