奶牛异或

奶牛异或

思路

利用前缀异或和，不断遍历加入树就行，
接下来的操作就跟查找异或最大值一模一样了，
无非就是在结束点标记上当前访问的是第几个数就行了。

代码

/*
    Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int trie[N * 30][2], num[N * 30], n, cnt;

void add(int value, int x) {
    int rt = 0;
    for(int i = 30; i >= 0; i--) {
        int now = value >> i & 1;
        if(!trie[rt][now]) trie[rt][now] = ++cnt;
        rt = trie[rt][now];
    }
    num[rt] = x;
}

pair<int, int> query(int value) {
    int rt = 0, ans = 0;
    for(int i = 30; i >= 0; i--) {
        int now = value >> i & 1;
        if(trie[rt][now ^ 1]) {
            ans |= 1 << i;
            rt = trie[rt][now ^ 1];
        }
        else {
            rt = trie[rt][now];
        }
    }
    return make_pair(ans, num[rt]);
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
//     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d", &n);
    int maxn = -1, l, r, sum = 0, a = 0;
    add(sum, 0);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a);
        sum ^= a;
        auto res = query(sum);
        add(sum, i);
        if(res.first > maxn) {
            maxn = res.first;
            l = res.second;
            r = i;
        }
    }
    printf("%d %d %d\n", maxn, l + 1, r);
    return 0;
}