最大异或和（可持久化01字典树）

题目：

给定一个非负整数序列 $\{ A \}$ ，初始长度为 $N$ 。
有 $M$ 个操作，有以下两种操作类型：
$A\space x$ ：添加操作，表示在序列末尾添加一个数 $x$ ，序列的长度 $N+1$ 。
$Q\space l \space r \space x$ ：询问操作，你需要找到一个位置 $p$ ，满足 $l \leq p \leq r$ ，使得： $A_p xor A_{p+1} xor \dots xor A_n xor X$ 最大，输出最大是多少。
$N≤3e5$

做法：

我们直接看查询操作，它是要求序列的某个后缀的 $xor$ 和， $xor$ $X$ 的最大值。我们设 $pre_i$ 表示序列前 $i$ 个数的 $xor$ 和。则其实是要求 $pre_{p-1}\space xor \space pre_n \space xor\space X$ 的最大值。而插入操作只是在末尾多加了一个数罢了，不会影响前面的 $pre$ ，处理容易。
由于 $pre_n$ 和 $X$ 在每次询问时都确定的，我们设 $Y = pre_n\space xor\space X$ ，则现在要解决的问题是：每个询问在 $[l,r]$ 区间中找一个 $p$ ，使 $pre_{p-1} \space xor \space Y$ 的值最大。假如没有区间的限制，就是一个 $01$ 字典树。而加了区间限制意味着我们每次询问需要的是只包含一段序列的 $01$ 字典树，所以需要用到可持久化 $01$ 字典树。当我们询问 $[l,r]$ 区间时，相当于用第 $r$ 个版本的树-第 $l-1$ 个版本的树得到 $[l，r]$ 区间的树。

代码：

#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;
const int N = 1e6 + 7;
const int M = 2e7 + 7;
int tot, root[N];
int T[M][2], sze[M][2];
void insert(int pre, int &now, int x, int dep){
    if (dep == -1) return;
    now = ++tot;
    int b = (x>>dep)&1;
    T[now][b^1] = T[pre][b^1], sze[now][b^1] = sze[pre][b^1];
    sze[now][b] = sze[pre][b]+1;
    insert(T[pre][b], T[now][b], x, dep-1);
}
int query(int l, int r, int x, int dep){
    if (dep == -1) return 0;
    int b = (x>>dep)&1;
    if (sze[r][b^1]-sze[l][b^1] > 0){
        return query(T[l][b^1], T[r][b^1], x, dep-1)+(1<<dep);
    }else{
        return query(T[l][b], T[r][b], x, dep-1);
    }
}
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    int xorsum = 0;
    for (int i = 1; i <= n; ++i){
        int x; cin >> x; xorsum ^= x;
        insert(root[i-1], root[i], xorsum, 30);
    }
    while (m--){
        string op; cin >> op;
        if (op == "A"){
            int x; cin >> x; xorsum ^= x;
            insert(root[n], root[n+1], xorsum, 30); n++;
        }else{
            int l, r, x; cin >> l >> r >> x;
            x ^= xorsum;
            if (r == 1) cout << x << endl;
            else cout << query(root[max(l-2, 0)], root[r-1], x, 30) << endl;
        }
    }
    return 0;
}