[P4735] 最大异或和——可持久化trie + 思维

给定n个数字，m个操作

操作1是往数组最后添加一个数字x

操作2是给出[L, R]，与数字x，输出在[L, R]中选一个数字p使得，a[p]^a[p+1]^...^a[n]^x的值最大

首先，考虑题目要求的是【1，R】的话，那么其实这道题无非就是可持久化trie + 前缀和异或而已。

但是问题就是有一个L。那么该如何处理这个L呢。我们考虑trie树的每一个节点多维护一个信息（以前没想过trie树每个节点还能带别的信息，这次学到了！

即经过的最大前缀和编号，那么我们在query的时候就只需要check一下当前点的最大前缀和编号是否小于L即可。（y总讲得真好

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5+10;
const int M = N*25;

int tr[M][2];
int root[N], sum[N];
int max_id[M];
int id;

void _insert(int k, int pre, int now) {
    max_id[now] = k;
    for (int i = 24; i >= 0; i --) {
        int v = sum[k] >> i & 1;
        if (pre) tr[now][v^1] = tr[pre][v^1];
        tr[now][v] = ++id;
        max_id[ tr[now][v] ] = k;
        now =  tr[now][v] ;
        pre =  tr[pre][v] ;
    }
}

int query(int val, int L, int now) {
    for (int i = 24; i >= 0; i --) {
        int v = val >> i & 1;
        if (max_id[tr[now][v^1]] >= L) now = tr[now][v^1]; //check一下当前点的最大前缀和编号是否小于L
        else now = tr[now][v];
    }
    return val ^ sum[max_id[now]];
}

int main() {
    int n, m; scanf("%d%d", &n, &m);
    
    root[0] = ++id;
    max_id[0] = -1; ///这里需要置成比0小的数，因为0这个编号其实是存在的（sum[0]），所以我们不能赋值为0
    _insert(0, 0, root[0]); ///这里需要插入0这个值的，因为这个是前缀和异或，那么就有sum[n] ^ 0的情况出现。

    int l, r, x;
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &x);
        root[i] = ++id;
        sum[i] = sum[i-1] ^ x;
        _insert(i, root[i-1], root[i]);
    }
    char op[2];
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            scanf("%d", &x);
            ++ n;
            root[n] = ++id;
            sum[n] = sum[n-1] ^ x;
            _insert(n, root[n-1], root[n]);
        }
        else {
            scanf("%d%d%d", &l, &r, &x);
            int ans = query(sum[n]^x, l-1, root[r-1]);
            printf("%d
", ans);
        }
    }
    return 0;
}