具体见注释

C++ 代码

#include <iostream>
using namespace std;
const int N = 600005, M = N * 25;

int n, m;
int s[N];
int tr[M][2], version[M];
int root[N], idx;

// 从左往右四个参数：当前版本, 这个数的第几位, 前一个版本对应的结点，当前版本的被处理的这个父结点
void insert(int i, int k, int p, int q)
{
    if (k < 0)
    {
        version[q] = i;
        return ;
    }
    int v = s[i] >> k & 1;   //  当前被处理的这一位数字
    if (p) tr[q][v ^ 1] = tr[p][v ^ 1];  // 如果前一个版本中,另一面存在(v ^ 1指和v相反的一侧) 那么把这一整块copy到当前版本的这个父节点下，v这一侧为新增的路径，需要新开辟。
    tr[q][v] = ++ idx;    // 给v开一个新节点
    insert(i, k - 1, tr[p][v], tr[q][v]);   //  以v这个结点为父节点，继续往下处理
    version[q] = i;   // q这个结点的版本即为最新版本
}

int query(int root, int C, int L)   // L为限制  即L ~ root之间的版本是符合要求的
{
    int p = root;
    for (int i = 23; i >= 0; i --)
    {
        int v = C >> i & 1;
        if (version[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }
    return C ^ s[version[p]];         // 最后找下来的叶结点的版本是多少，说明目标数即为第几次插入的那个数
}

int main()
{
    scanf("%d%d", &n, &m);
    // 这儿用到了前缀和，  因此s[0]也是合法的版本， 置为-1
    version[0] = -1;   //这一步不可省略， 假如某个结点没有被插入过， 那么它的版本就置为 -1，  结合query中， if (version[tr[p][v ^ 1]] >= L)， 假如tr[p][v ^ 1] == 0,即这个节点不存在，那么它的版本就应该是-1，不然就会出问题
    // 每棵树最上面的根节点都是一个空结点
    root[0] = ++ idx;
    insert(0, 23, 0, root[0]);

    for (int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
        root[i] = ++ idx;
        insert(i, 23, root[i - 1], root[i]);
    }
    char op[2];
    int l, r, x;
    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;
}