分析

• 我们定义前缀和$S_i$，表示前i个数的前缀和，第一个数据存储在$a_1$中，即（$\bigoplus$表示异或）：

$$ S_0 = 0 \\ S_1 = a_1 \\ S_2 = a_1 \bigoplus a_2 \\ … \\ S_i = a_1 \bigoplus a_2 \bigoplus a_3 ......\bigoplus a_i $$

• 这样定义之后，我们需要求解的内容就可以变为：

$$ a_p \bigoplus ......\bigoplus a_n \bigoplus x = S_{p-1} \bigoplus S_N \bigoplus x $$

• 上面的式子中我们可以将$S_N \bigoplus x$看成常数，记为C，则相当于让我们在区间$[L, R]$中找到一个p，使得$S_{p-1} \bigoplus C$的值最大。

• 类似于AcWing 143. 最大异或对，关于这题的讲解可以参考：网址。我们可以将每个数据$a_i$看成一个二进制的字符串，因为$0 \le a[i] \le 10^7$，又$2^{23} \le a[i] \le 2^{24}$，因此我们需要将每个数据对应到一个长度为24为的01二进制串上。

• 我们可以先考虑一个简单的情况，假设让我们从$[1, R]$中找到一个这样的p的话，问题就十分类似于AcWing 143. 最大异或对，不同点在于本题中的a数组是不断变化的，因此我们要记录下来所有历史版本的trie树，root[R]中存储的就是插入a[1~R]形成的trie树。

• 如果区间左边的限制也加上，则问题就变成了让我们在区间$[L, R]$中找到一个p，使得$S_{p-1} \bigoplus C$的值最大，我们可以这样处理：在trie树中的每个节点中多记录一个信息max_id，表示以当前节点为根的子树所代表的数据中最晚插入的那个数据插入的时间t（即第几个插入的），如果$t \ge L$，则说明这棵子树在$[L, R]$这个区间中存在。

• 对于上面提到的某个C，数据A可以看成一个24的二进制字符串，从左到右遍历这个字符串，假设当前考察的是字符t，则在trie树中我们应该走到1^t的分支上（如果存在的话，即对于区间$[L, R]$，如果该分支对应的max_id$\ge$L，则说明存在），这样异或值才能最大（贪心思想）。

• 原序列长度为$3 \times 10 ^5$，因为操作的个数最多也是$3 \times 10 ^5$，因此序列的长度最大是$6 \times 10 ^5$。另外还需要考虑trie中节点的个数：每次操作最多建立24个节点，再加上根节点，一共25个节点，每个数据最多建立25个节点，因此节点数为$25 \times 6 \times 10 ^ 5 = 1.5 \times 10 ^ 7$，每个节点两个分支，因此第二维为2；另外还需要记录每个点的max_id，需要的空间量是$1.5 \times 10 ^ 7 \times 3 = 4.5 \times 10 ^ 7$个int，大约$4.5 \times 10 ^ 7 \times 4 / 10 ^ 6 = 180$MB的存储空间，题目提供256MB的存储空间，满足要求。

• 一个trick：如果trie算完之后题目要求的空间不足怎么办，我们可以反推trie开多少节点。

• 核心思想：所有需要修改的节点，不要去修改它，而是拷贝一个新的，然后修改这个新点。

• 这里trie中的0既代表根节点又代表空节点。

#include <iostream>

using namespace std;

const int N = 600010, M = N * 25;

int n, m;  // 序列初始长度、操作个数
int s[N];  // 原序列的异或前缀和
int tr[M][2];  // trie中的节点
int max_id[M];  // 以当前节点为根的子树所代表的数据中最晚插入的那个数据插入的时间t(即第几个插入的)
int root[N], idx;  // 记录每个版本，从1开始

// i: 前缀和下标, 表示插入Si
// k: 当前处理到Si的第几位, 从23为开始处理到第0位
// p: 上一个版本的根节点
// q: 当前版本的根节点, 是p的复制, 差别在于新加了一条链
void insert(int i, int k, int p, int q) {

    if (k < 0) {  // 说明我们处理完了最后一位(第0位), 此时q就是叶节点的编号
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    // 所有需要修改的节点，不要去修改它，而是拷贝一个新的，然后修改这个新点。
    if (p) tr[q][v ^ 1] = tr[p][v ^ 1];  // 如果上一个版本存在，直接复制过来
    tr[q][v] = ++idx;  // 当前这个二进制位需要开辟一个新的节点
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);  // 左右儿子取大
}

// 从root开始查询, 需要被异或的数据是C, 区间左端点是L
int query(int root, int C, int L) {

    int p = root;
    for (int i = 23; i >= 0; i--) {
        int v = C >> i & 1;
        if (max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];  // 找不到更好的了，只能将就一下
    }
    return C ^ s[max_id[p]];  // 这个叶子节点只有它自己，因此max_id就是Si的下标i
}

int main() {

    scanf("%d%d", &n, &m);

    // 这里max_id[0]中的0表示空节点，空节点不包含任何点，
    // 所以它的max_id需要设置成比所有的id都小的数，所以设置成任何负数均可。
    max_id[0] = -1;

    root[0] = ++idx;  // 第0个版本在trie中的根节点编号为1
    insert(0, 23, 0, root[0]);  // 在第0个版本中插入S0, 不存在上一个版本

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

    char op[2];
    int l, r, x;
    for (int i = 1; i <= m; i++) {
        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);
            // p在[L, R]之间，p-1在[L-1, R-1]之间
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }

    return 0;
}