最大异或和

题意：
给定一个非负整数序列，初始长度为。
有个操作，有以下两种操作类型： ：添加操作，表示在序列末尾添加一个数，序列的长度。 ：询问操作，你需要找到一个位置，满足，使得： 最大，输出最大是多少。
数据范围：

题解：
可持久化模板题。
记前缀异或和为：
由于异或的性质，
类似主席树的建树，对每个前缀建立一棵树。
先考虑对于，使得 最大。
那么只需要异或上一个前缀使得答案最大即可，即在第棵树上上找到这个前缀即可。
现在，故需要对树上的每个结点记录一个用于判断当前这个结点的集合中有没有大于等于的数。

代码：

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

const int N = 6e5 + 10;
const int M = N * 25;
int tr[M][2], maxid[M], root[N], idx;
int s[N], n, m;

void insert(int i, int k, int p, int q) {
    if(k < 0) {
        maxid[q] = i;
        return ;
    }

    int u = s[i] >> k & 1;
    if(p) tr[q][!u] = tr[p][!u];
    tr[q][u] = ++idx;
    insert(i, k - 1, tr[p][u], tr[q][u]);
    maxid[q] = max(maxid[tr[q][0]], maxid[tr[q][1]]); 
}

int query(int root, int C, int L) {
    int p = root;
    for(int i = 23; i >= 0; --i) {
        int u = C >> i & 1;
        if(maxid[tr[p][!u]] >= L) p = tr[p][!u];
        else p = tr[p][u];
    }
    return C ^ s[maxid[p]];
} 

int l, r, x;
char op[2];
int main()
{
    scanf("%d%d", &n, &m);

    maxid[0] = -1;
    root[0] = ++idx;
    insert(0, 23, 0, root[0]);

    for(int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
        root[i] = ++idx;
        insert(i, 23, root[i - 1], root[i]);
    }

    while(m--) {
        scanf("%s", op);
        if(*op == 'A') {
            scanf("%d", &x);
            ++n;
            s[n] = s[n - 1] ^ x;
            root[n] = ++idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else {
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }
    return 0;
}