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

题目：

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

做法：

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

代码：

#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;
}