可持久化 Trie

依旧不给图。

可持久化一般解决的是区间查询类的问题。

可持久化 Trie 基本上都是按着 01 Trie 搞的。

怎么建一棵可持久化 Trie 呢？

考虑到：如果两个相邻版本的前缀相同的话，我们就从后一个版本当前节点往上一个版本的子节点上连一条边，这样我们就可以保证从每一个根节点出发都可以将所有的版本都过一遍。

先丢个例题：LuoguP4735

经过一番思考，我们令 s[i] 表示序列到 i 的前缀异或和。

令选择的节点为 p，那么我们无非要找到最大的 $s[p - 1]\ xor\ x\ xor\ s[n]$，那么我们就可以直接在 l-1 和 r-1 两个范围里边找到值就可以了。

令 $val = s[n] \operatorname{xor}\ x$。

如果只有 $p\ \le r - 1$ 的限制，我们直接用可持久化 01 trie，因为可持久化 01trie 上保存到的是 $\forall\ i \in [0, n], s[0-i]$ 这些二进制数构成的 01trie，我们每次从 r-1 出发，优先找 val 当前位相反的就可以了。

如果加上 l-1 的限制，我们需要在节点上维护一些信息，设 end[p] 表示 Trie 的节点 p 是序列 s 中第几个二进制数的末尾节点（如果不是末尾就设成 -1）。lat[p] 表示以 p 为根节点的子树内最大的 end 值，如果遇上一个 lat[p] 比 l-1 小的那么我们就不能去了。

这样我们就解决了这个问题。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 600005;

int trie[N * 24][2], lat[N * 24];
int s[N], rt[N], n, m, tot;

// end 和 lat 可以合成一个数组用的呢
void add(int i, int k, int p, int q) { // i 是 s[i] 的编号，k 是第几位，p 是上一版本的根，q 是这一版本的根
    if(k < 0) { // 如果插完了就返回
        lat[q] = i; // 将最大的值标记一下
        return ;
    }

    int c = (s[i] >> k) & 1; // 提取出当前位上的二进制数
    if(p) trie[q][c ^ 1] = trie[p][c ^ 1]; // 如果 p 不为零的话
                                           // 我们尝试用 c^1 那个儿子去连过去
                                           // 因为 c 要用来向下存，而我们一共只有两个儿子
                                           // 在不考虑前后缀的情况下直接去赋值
                                           // 哪怕前缀不相等，节点编号也是 0（因为你并没有在上一个版本建这个节点）
                                           // 因此我们是不需要畏惧的！
    trie[q][c] = ++tot; // 新开节点
    add(i, k - 1, trie[p][c], trie[q][c]); // 递归建下一个节点
    lat[q] = max(lat[trie[q][0]], lat[trie[q][1]]); // 回溯的时候向上更新
}

int ask(int now, int val, int k, int lim) { // now 是到了哪个节点，k 是位数，lim 是 l - 1
    if(k < 0) return s[lat[now]] ^ val; // 如果查完了就只能返回当前子树中最大的值了
    int c = (val >> k) & 1; // 取出当前位
    if(lat[trie[now][c ^ 1]] >= lim) return ask(trie[now][c ^ 1], val, k - 1, lim); // 如果可以走的话，就走过去
    else return ask(trie[now][c], val, k - 1, lim); // 否则就只能走另一个
}

int main() {
    n = rd(), m = rd();
    lat[0] = -1;
    rt[0] = ++tot; // 先弄个新节点出来
    add(0, 23, 0, rt[0]); // 先把 0 插进去免掉分类讨论

    for(int i = 1; i <= n; ++i) {
        int x = rd();
        s[i] = s[i - 1] ^ x;
        rt[i] = ++tot;
        add(i, 23, rt[i - 1], rt[i]); // 正经插入
    }

    for(int i = 1; i <= m; ++i) {
        char opt;
        cin >> opt;
        if(opt == 'A') {
            int x = rd();
            rt[++n] = ++tot;
            s[n] = s[n - 1] ^ x;
            add(n, 23, rt[n - 1], rt[n]);
        } else {
            int l = rd(), r = rd(), x = rd();
            printf("%d\n", ask(rt[r - 1], x ^ s[n], 23, l - 1));
        }
    }
    return 0;
}